过样例

下载测试点1测试发现和答案一样

但是提交时没对

大佬求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,q,op,x,y,c[N],dfn[2*N],st[N],en[N],tot,fa[N][25],b[N],q1,tim,vis[N];
bool used[N];
ll v[N],w[N],ans[N],temp,cnt[N];
vector<int> g[N];
struct Query{
    int l,r,t,id,lca;
    Query(){}
    Query(int _l,int _r,int _t,int _id,int _lca):l(_l),r(_r),t(_t),id(_id),lca(_lca){}
    bool operator < (const Query &p)const{
        return b[l]==b[p.l]?(b[r]==b[p.r]?t<p.t:b[r]<b[p.r]):b[l]<b[p.l];
    }  
}p[N];
struct Modi{
	int p,f;
	Modi(){}
	Modi(int _p,int _f):p(_p),f(_f){}
}modi[N];
void dfs(int x,int father){
	st[x]=++tot;
    dfn[tot]=x;
    fa[x][0]=father;
    for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=0;i<g[x].size();i++){
        int son=g[x][i];
        if(son==father) continue;
        dfs(son,x);
    }
    en[x]=++tot;
    dfn[tot]=x;
}
int LCA(int x,int y){
	if(x==y) return x;
	if(st[x]>st[y]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(st[fa[y][i]]>st[x]){
			y=fa[y][i];
		}
	return fa[y][0];
}
void add(int x){
    vis[x]++;
    if(vis[x]==1){
    	cnt[c[x]]++;
    	used[x]=true;
    	temp+=w[cnt[c[x]]]*v[c[x]];
    }
    if(vis[x]==2){
		temp-=w[cnt[c[x]]]*v[c[x]];
    	cnt[c[x]]--;
    	used[x]=false;
    }
}
void del(int x){
   	vis[x]--;
    if(vis[x]==1){
    	cnt[c[x]]++;
    	used[x]=true;
    	temp+=w[cnt[c[x]]]*v[c[x]];
    }
    if(!vis[x]){
		temp-=w[cnt[c[x]]]*v[c[x]];
    	cnt[c[x]]--;
    	used[x]=false;
    }
}
void modify(int t){
	int x=modi[t].p,y=modi[t].f;
	if(used[x]){
		temp-=w[cnt[c[x]]]*v[c[x]];
    	cnt[c[x]]--;
		cnt[y]++;
    	temp+=w[cnt[y]]*v[y];
	}
	swap(c[x],modi[t].f);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    ll bs=cbrt(1ll*n*n);
	for(int i=1;i<=m;i++) scanf("%lld",&v[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=2*n;i++) b[i]=(i-1)/bs+1;
	dfs(1,0);
	while(q--){
		scanf("%d%d%d",&op,&x,&y);
		if(op==1){
			if(st[x]>st[y]) swap(x,y);
			int lca=LCA(x,y);
			if(lca==x) p[++q1]=Query(st[x],st[y],tim,q1,0);
			else p[++q1]=Query(en[x],st[y],tim,q1,lca);
		} 
		else modi[++tim]=Modi(x,y);
	}
	sort(p+1,p+q1+1);
	int l=1,r=0,t=0;
	for(int i=1;i<=q1;i++){
		while(r<p[i].r) add(dfn[++r]);
		while(r>p[i].r) del(dfn[r--]);
        while(l<p[i].l) del(dfn[l++]);
		while(l>p[i].l) add(dfn[--l]);
        while(t<p[i].t) modify(++t);
        while(t>p[i].t) modify(t--);
		if(p[i].lca) add(p[i].lca);
        ans[p[i].id]=temp;
        if(p[i].lca) del(p[i].lca);
	}
	for(int i=1;i<=q1;i++) printf("%lld\n",ans[i]);
    return 0;
}