CF734E Anton and Tree

2018-11-02 07:33:15


题意:一棵树,每个点是黑色或白色,每次可以选择一个颜色相同的连通块把颜色反转,问最少几次操作可以让所有点颜色相同


树形 $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;
}