CF734E Anton and Tree

题意：一棵树，每个点是黑色或白色，每次可以选择一个颜色相同的连通块把颜色反转，问最少几次操作可以让所有点颜色相同 ------------ 树形$dp?$ 好像不是很可做 既然每次选择的是一个颜色相同的连通块 那就把颜色相同且相邻的点缩成一个点 用并查集实现 然后发现答案是$(D+1)/2$ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=2e5+5; struct node { int to,nxt; }edge[N<<1]; int n,num,head[N],w[N],fa[N],f[N],g[N],D,fr[N],to[N],pos; bool vis[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; edge[++num]=(node){from,head[to]}; head[to]=num; } int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void dfs(int k,int fa,int dh) { if (dh>D) D=dh,pos=k; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v!=fa) dfs(v,k,dh+1); } } int main() { n=read(); for (reg int i=1;i<=n;i++) w[i]=read(),fa[i]=i; for (reg int i=1;i<n;i++) { fr[i]=read(),to[i]=read(); if (!(w[fr[i]]^w[to[i]])) fa[find(fr[i])]=find(to[i]); } for (reg int i=1;i<n;i++) { int u=find(fr[i]),v=find(to[i]); if (u!=v) add_edge(u,v); } dfs(fa[1],0,0); dfs(pos,0,0); printf("%d\n",(D+1)>>1); return 0; } ```