题目:
UOJ也能评测
题解
请看代码
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> typedef long long ll; using namespace std; const int N = 1e5 + 3; int n,m,Q,q,V[N],col[N],sum[N],last[N],blk[N]; int S,Bsum,Log[N],que[N],dep[N],fa[N][18]; int Tp[N],A[N],B[N],cc[N]; int tot,info[N],nxt[N*2],go[N*2]; ll cur,ans[N],W[N]; bool sta[N];//sta数组记录这个节点是否在cur的计算中 int read() { int ret=0,neg=1;char j=getchar(); for (;j>'9' || j<'0';j=getchar()) if (j=='-') neg=-1; for (;j>='0' && j<='9';j=getchar()) ret=ret*10+j-'0'; return ret*neg; } struct node { int x,y,bl,br,id; bool operator < (const node &k)const { if (bl!=k.bl) return bl<k.bl; if (br!=k.br) return br<k.br; return id<k.id; } }qry[N]; void add(int x,int y) { nxt[++tot]=info[x];info[x]=tot;go[tot]=y; nxt[++tot]=info[y];info[y]=tot;go[tot]=x; } void Dfs(int x,int F) { int y,st=tot;dep[x]=dep[F]+1;fa[x][0]=F; for (int i=0;fa[x][i];i++) fa[x][i+1]=fa[fa[x][i]][i]; for (int k=info[x];y=go[k],k;k=nxt[k]) if (y!=F) { Dfs(y,x); if (tot-st>=S) { while (tot>st) blk[que[tot--]]=Bsum; ++Bsum; } } que[++tot]=x; } int LCA(int x,int y) { if (dep[x]<dep[y]) swap(x,y); int d=dep[x]-dep[y]; for (int i=Log[d];i>=0;i--) if (1<<i&d) x=fa[x][i]; if (x==y) return x; for (int i=Log[dep[x]];i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void Rev(int x)//取反操作 { cur-=W[sum[col[x]]]*V[col[x]]; sta[x]?--sum[col[x]]:++sum[col[x]]; sta[x]=!sta[x]; cur+=W[sum[col[x]]]*V[col[x]]; } void Modify(int x,int y) { if (!sta[x]) return (void)(col[x]=y); Rev(x);col[x]=y;Rev(x); } void Log_Init() { Log[0]=-1; for (int i=1;i<=n;i++) Log[i]=Log[i>>1]+1; } void Solve(int x,int y) { int Lca=LCA(x,y); while (x!=Lca) Rev(x),x=fa[x][0];//把路径上的点取反 while (y!=Lca) Rev(y),y=fa[y][0]; } void upt(int tarT,int curT) { while (curT < tarT) { ++curT; if (!Tp[curT]) Modify(A[curT], B[curT]);//进行修改 } while (curT > tarT) { if (!Tp[curT]) Modify(A[curT], last[curT]);//撤销修改 --curT; } } int main() { n=read();m=read();Q=read();S=pow(n,2.0/3.0); //S是块的大小 for (int i=1;i<=m;i++) V[i]=read(); for (int i=1;i<=n;i++) W[i]=read(),W[i]+=W[i-1]; for (int i=1;i<n;i++) add(read(),read()); for (int i=1;i<=n;i++) cc[i]=col[i]=read(); tot=0;Log_Init();Dfs(1,0); //以出栈顺序作为Dfs序,并处理每个点在哪一块，块从0标号 while (tot) blk[que[tot--]]=Bsum-1; for (int i=1;i<=Q;i++) { Tp[i]=read();A[i]=read();B[i]=read(); if (Tp[i]) { qry[++q].id=i; if (blk[A[i]]>blk[B[i]]) swap(A[i],B[i]);//保证a[i]的块在b[i]左边 qry[q].x=A[i];qry[q].y=B[i];qry[q].bl=blk[A[i]];qry[q].br=blk[B[i]]; } else last[i]=cc[A[i]],cc[A[i]]=B[i];//记录修改操作前后是啥 } sort(qry+1,qry+q+1);qry[0].x=qry[0].y=1; for (int i=1;i<=q;i++) { upt(qry[i].id,qry[i-1].id);//更新/撤销上一个询问到这个询问中间的修改操作 Solve(qry[i].x,qry[i-1].x);Solve(qry[i].y,qry[i-1].y); //从上次询问的点移动到这次的询问并更新cur int L=LCA(qry[i].x,qry[i].y); Rev(L);ans[qry[i].id]=cur;Rev(L); } for (int i=1;i<=Q;i++) if (Tp[i]) printf("%lld ",ans[i]); return 0; }