自动搬运

查看原文

来自洛谷，原作者为

	ssfx2019s005 noip2024 rp++

搬运于2025-08-24 23:05:44，当前版本为作者最后更新于2024-11-07 21:12:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法：树的直径

首先，颜色相同的两个点之间的边，无论如何都不会被经过，因此直接忽略即可。颜色不同的两个点之间的边，我们保留它并让它的边权为 $1$。

这样，这棵树就被分成了若干个连通块，其中每个连通块都是一棵树。容易发现每个连通块中最长的路径就是它的直径。因此，对每颗树求出直径后最大的直径即为所求。

code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2e5+15;
int col[N];
int e[N],ne[N],h[N],idx,w[N];
int f[N],g[N],mxl;
int n;
int dfn[N],timestamp;
void add_in(int x,int y,int z){
	e[++idx]=y; ne[idx]=h[x]; w[idx]=z; h[x]=idx;
} 
void dfs(int u,int fa){ //树的直径
	dfn[u]=++timestamp; //记录一下访问了该节点
	int v;
	f[u]=0;
	for(int i=h[u];i;i=ne[i]){
		v=e[i];
		if(v==fa) continue;
		dfs(v,u);
		mxl=max(mxl,f[u]+f[v]+w[i]);
		f[u]=max(f[u],f[v]+w[i]);
	} 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>col[i];
	}
	int x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		if(col[x]==col[y]) continue; //两点颜色相同则不用建边
		add_in(x,y,1);
		add_in(y,x,1);
	}
	int res=0;
	for(int i=1;i<=n;i++){
		if(!dfn[i]) //该节点未被访问过
			dfs(i,0);
	}
	cout<<mxl+1<<endl; //因为树的直径计算的是经过边的条数，因此需+1
	return 0;
}