CodeForces-734E Anton and Tree 树的直径

题目大意:

给定一棵有n个节点的树,有黑点白点两种节点.

每一次操作可以选择一个同种颜色的联通块将其染成同一种颜色

现在给定一个初始局面问最少多少步可以让树变为纯色.

题解:

首先我们拿到这棵树时先将其缩点

然后我们手中的树就变成了一棵黑白相间的黑白树.

那么我们现在就是每次选择一个节点使其变色,都会使得这个节点相邻的所有节点合并进来.

所以我们找度数最大的合并就好了啊

我们现在把这棵树想象成由若干条路径组成的.

那么我们每次合并都会使某些路径的长度最多减少2

所以我们可以自然而然地想到一定是树的直径花费的操作次数最大.

所以我们将一棵树化作一条链上面连着许多其他的分支的形式.

手模几个样例就话发现答案实际上是\([\frac{len+1}{2}]\)len为直径长度.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 200010;

int belong[maxn],nodecnt;

int col[maxn];

struct Graph{

    struct Edge{

	int to,next;

    }G[maxn<<1];

    int head[maxn],cnt;

    void add(int u,int v){

	G[++cnt].to = v;

	G[cnt].next = head[u];

	head[u] = cnt;

    }

#define v G[i].to

    void dfs1(int u,int f){

	if(col[u] != col[f]) belong[u] = ++ nodecnt;

	else belong[u] = belong[f];

	for(int i = head[u];i;i=G[i].next){

	    if(v == f) continue;

	    dfs1(v,u);

	}return ;

    }

    int dis[maxn],p;

    void dfs2(int u,int f){

	for(int i = head[u];i;i=G[i].next){

	    if(v == f) continue;

	    dis[v] = dis[u] + 1;

	    dfs2(v,u);

	}

	if(dis[p] < dis[u]) p = u;

    }

#undef v

}g1,g2;

int main(){

    int n;read(n);

    for(int i=1;i<=n;++i) read(col[i]);

    for(int i=1,u,v;i<n;++i){

	read(u);read(v);

	g1.add(u,v);g1.add(v,u);

    }belong[1] = ++ nodecnt;

    g1.dfs1(1,1);

    for(int u=1;u<=n;++u){

	for(int i = g1.head[u];i;i=g1.G[i].next){

	    if(belong[g1.G[i].to] != belong[u]){

		g2.add(belong[u],belong[g1.G[i].to]);

	    }

	}

    }

    g2.dfs2(1,1);

    int u = g2.p;

    memset(g2.dis,0,sizeof g2.dis);

    g2.dfs2(u,u);

    int ans = (g2.dis[g2.p] + 1)/2;

    printf("%d\n",ans);

    return 0;

}

巴特西

CodeForces-734E Anton and Tree 树的直径

题目大意:

题解:

最新文章

热门文章