题目链接：点击查看
题目大意：给出一棵 n 个节点构成的数，每个节点都有一个颜色，现在需要执行 m 次操作，每次操作分为如下两种类型：
Q x：回答所有颜色为 x 的节点构成的连通子图含有的最少边数U x y：将点 x 的颜色修改为 y题目分析：首先转换模型，要求边的个数，不妨转换成距离
根据虚树建树得到启发，如果目前只有两个节点的话，那么该题对应的答案显然是两点之间的距离，对应为下图：
如果此时再加入一个点 2，满足 dfn[ 1 ] < dfn[ 2 ] < dfn[ 3 ]，那么对于点 2 来说无非只有两种情况：
不位于点 1 到点 3 的路径上位于点 1 到点 3 的路径上分别对应着下图的两种情况：
对于情况二来说，在本题中对答案显然不做贡献，而对于情况一来说，多出来的一段贡献已经用红圈标记出来了
总结一下求这个红圈中的贡献，实质上就是求 dis( 1 , 2 ) + dis( 2 , 3 ) - dis( 1 , 3 )
其中，dis( x , y ) 是从点 x 到点 y 的距离，这个借助 LCA 很容易就能实现，这样本题的做法就呼之欲出了
求出整棵树的 dfs 序，将每个颜色的节点按照 dfs 序维护，对于每个节点 x 来说，设 l 为 dfs 序小于 x 的最大节点，r 为 dfs 序大于 x 的最小节点，mmin 为颜色 c[ x ] 中 dfs 序最小的节点，mmax 为颜色 c[ x ] 中 dfs 序最大的节点，加入点 x 分为两种情况讨论：
如果 l 和 r 都存在：ans += dis( x , l ) + dis( x , r ) - dis( l , r )，对应着上图中的情况否则：ans += dis( x , mmin ) + dis( x , mmax ) - dis( mmin , mmax )，对应着新加入的点的 dfn 为最小值或最大值的情况，此时该点对本题的答案一定具有贡献，随便找两个点配合更新一下答案即可删除的话倒着减去贡献就好了
代码：
//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=1e5+100; int limit,deep[N],dp[N][20],id[N],c[N],ans[N],cnt; vector<int>node[N]; struct Scmp { bool operator()(int x,int y) { return id[x]<id[y]; } }; set<int,Scmp>st[N]; void dfs(int u,int fa,int dep) { id[u]=++cnt; deep[u]=dep; dp[u][0]=fa; for(int i=1;i<=limit;i++) dp[u][i]=dp[dp[u][i-1]][i-1]; for(auto v:node[u]) { if(v==fa) continue; dfs(v,u,dep+1); } } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); for(int i=limit;i>=0;i--) if(deep[x]-deep[y]>=(1<<i)) x=dp[x][i]; if(x==y) return x; for(int i=limit;i>=0;i--) if(dp[x][i]!=dp[y][i]) { x=dp[x][i]; y=dp[y][i]; } return dp[x][0]; } int dis(int x,int y) { return deep[x]+deep[y]-2*deep[LCA(x,y)]; } void update(int x,int flag) { if(flag==-1) st[c[x]].erase(x); auto it=st[c[x]].lower_bound(x); if(st[c[x]].empty()) ans[c[x]]=0; else if(it==st[c[x]].begin()||it==st[c[x]].end()) { ans[c[x]]+=flag*dis(*st[c[x]].begin(),x); ans[c[x]]+=flag*dis(*st[c[x]].rbegin(),x); ans[c[x]]-=flag*dis(*st[c[x]].begin(),*st[c[x]].rbegin()); } else { auto nt=it,pre=--it; ans[c[x]]+=flag*dis(*nt,x); ans[c[x]]+=flag*dis(*pre,x); ans[c[x]]-=flag*dis(*pre,*nt); } if(flag==1) st[c[x]].insert(x); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n; scanf("%d",&n); limit=log2(n)+1; for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); node[u].push_back(v); node[v].push_back(u); } dfs(1,0,0); for(int i=1;i<=n;i++) { scanf("%d",c+i); update(i,1); } int m; scanf("%d",&m); while(m--) { char op[5]; scanf("%s",op); if(op[0]=='Q') { int x; scanf("%d",&x); printf("%d\n",st[x].empty()?-1:ans[x]/2); } else { int x,y; scanf("%d%d",&x,&y); update(x,-1); c[x]=y; update(x,1); } } return 0; }
