CF734E Anton and Tree（并查集+树的直径）
题目链接：https://www.luogu.com.cn/problem/CF734E
首先用并查集将题目中原先的相邻的颜色相同的点进行缩点，用并查集来完成。然后考虑如何改变是最优的。将缩点后的点建树，找到树的直径，不断改变直径的中点及其相邻颜色块的颜色，会让整个树在floor(len+1)次完成改变全部颜色（len为直径长度）。其他不是直径的枝叶会在改变直径时直接改变掉。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int N=200005; 9 int n,tot,maxd; 10 queue<int> q; 11 int x[N],y[N],c[N],head[N],f[N],vis[N],d[N]; 12 struct node{ 13 int to,next; 14 }edge[N<<1]; 15 void init(){ 16 memset(head,-1,sizeof(head)); 17 } 18 int find(int x){ 19 if(f[x]!=x) f[x]=find(f[x]); 20 return f[x]; 21 } 22 void add(int u,int v){ 23 edge[tot].next=head[u]; 24 edge[tot].to=v; 25 head[u]=tot++; 26 } 27 int BFS(int s){ 28 int pos; 29 maxd=0; 30 memset(d,0,sizeof(d)); 31 memset(vis,0,sizeof(vis)); 32 while(!q.empty()) q.pop(); 33 q.push(s); vis[s]=1; 34 while(!q.empty()){ 35 int u=q.front(); q.pop(); 36 for(int i=head[u];i!=-1;i=edge[i].next){ 37 int v=edge[i].to; 38 if(vis[v]) continue; 39 vis[v]=1; 40 d[v]=d[u]+1; 41 q.push(v); 42 if(maxd<d[v]){ 43 maxd=d[v]; 44 pos=v; 45 } 46 } 47 } 48 return pos; 49 } 50 int main(){ 51 init(); 52 scanf("%d",&n); 53 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 54 for(int i=1;i<=n;i++) f[i]=i; 55 for(int i=1;i<n;i++){ 56 scanf("%d%d",&x[i],&y[i]); 57 int r1=find(x[i]),r2=find(y[i]); 58 if(c[r1]==c[r2]) f[r1]=r2; 59 } 60 for(int i=1;i<=n;i++) f[i]=find(f[i]);//缩点 61 for(int i=1;i<n;i++) if(f[x[i]]!=f[y[i]]) add(f[x[i]],f[y[i]]),add(f[y[i]],f[x[i]]); 62 int l=BFS(f[x[1]]); 63 BFS(l); 64 int ans=floor((maxd+1)/2); 65 printf("%d",ans); 66 return 0; 67 }