Description
Solution
树上带修改莫队…！VFK的题解写得很清楚啦
（我的程序为什么跑得这么慢…交的时候总有一种自己在卡测评的感觉…）
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #define MAXN 100005 typedef long long LL; using namespace std; int n,m,q,block,head[MAXN],cnt=0,tot1=0,tot2=0,vis[MAXN]; int v[MAXN],c[MAXN],last[MAXN],deep[MAXN],p[MAXN][20]; int stack[MAXN],top=0,belong[MAXN],tot3=0,num[MAXN]; LL w[MAXN],ans=0,res[MAXN]; struct Node1 { int next,to; }Edges[MAXN*2]; struct Node2 { int l,r,tim,id; Node2(int l=0,int r=0,int tim=0,int id=0):l(l),r(r),tim(tim),id(id){} bool operator < (const Node2& x) const { if(belong[l]==belong[x.l]) { if(belong[r]==belong[x.r]) return tim<x.tim; else return belong[r]<belong[x.r]; } else return belong[l]<belong[x.l]; } }query[MAXN]; struct Node3 { int pos,col,pre; Node3(int pos=0,int col=0,int pre=0):pos(pos),col(col),pre(pre){} }modify[MAXN]; void addedge(int u,int v) { Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; } int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+c-'0';c=getchar(); } return x*f; } void dfs(int u) { int now=top; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(p[u][0]==v)continue; p[v][0]=u; deep[v]=deep[u]+1; dfs(v); if(top-now>=block) { ++tot3; while(top!=now)belong[stack[top--]]=tot3; } } stack[++top]=u; } void init() { for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n;j++) p[j][i]=p[p[j][i-1]][i-1]; } int lca(int x,int y) { if(deep[x]>deep[y])swap(x,y); int f=deep[y]-deep[x]; for(int i=0;(1<<i)<=f;i++) if(f&(1<<i))y=p[y][i]; if(x!=y) { for(int i=(int)log2(n);i>=0;i--) if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i]; x=p[x][0]; } return x; } void calc(int pos) { if(vis[pos]) { ans-=1LL*v[c[pos]]*w[num[c[pos]]]; --num[c[pos]]; ans+=1LL*v[c[pos]]*w[num[c[pos]]]; } else { ans-=1LL*v[c[pos]]*w[num[c[pos]]]; ++num[c[pos]]; ans+=1LL*v[c[pos]]*w[num[c[pos]]]; } vis[pos]^=1; } void change(int pos,int col) { if(vis[pos]) calc(pos),c[pos]=col,calc(pos); else c[pos]=col; } void move(int x,int y) { if(deep[x]>deep[y])swap(x,y); while(deep[x]<deep[y]) calc(y),y=p[y][0]; while(x!=y){calc(x),calc(y);x=p[x][0],y=p[y][0];} } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(),q=read(); block=pow(n,2.0/3); for(int i=1;i<=m;i++)v[i]=read(); for(int i=1;i<=n;i++)w[i]=w[i-1]+read(); for(int i=1;i<n;i++) {int u=read(),v=read();addedge(u,v),addedge(v,u);} for(int i=1;i<=n;i++)last[i]=c[i]=read(); for(int i=1;i<=q;i++) { int t=read(),x=read(),y=read(); if(t) ++tot1,query[tot1]=Node2(x,y,tot2,tot1); else modify[++tot2]=Node3(x,y,last[x]),last[x]=y; } dfs(1),init(); while(top)belong[stack[top--]]=tot3; sort(query+1,query+1+tot1); int u=1,v=1; for(int i=1;i<=tot1;i++) { for(int j=query[i-1].tim+1;j<=query[i].tim;j++) change(modify[j].pos,modify[j].col); for(int j=query[i-1].tim;j>query[i].tim;j--) change(modify[j].pos,modify[j].pre); if(u!=query[i].l)move(u,query[i].l),u=query[i].l; if(v!=query[i].r)move(v,query[i].r),v=query[i].r; int t=lca(u,v); calc(t); res[query[i].id]=ans; calc(t); } for(int i=1;i<=tot1;i++) printf("%lld ",res[i]); return 0; }