题目：点击打开链接
题意：给出n个点，n-1条边构成一棵生成树，每个点都有黑白两种颜色，每次改变颜色都能使同颜色的相邻点改变颜色，求最小改变颜色的次数
分析：因为每次改变颜色都能使同颜色的相邻点改变颜色，所以相邻且颜色相同的点可以缩成一点，重新建图，构成黑白相间的点的树，设树的直径(任意两点的最远距离)为d，因为每次改变颜色都会使它与相邻的点的颜色相同，所以取树的直径上的点操作，共有d+1个点，因为点是黑白相间的，所以最少取(d+1)/2个点，一些枝叶上的点都会在直径上的点改变颜色的时候改变成相同颜色。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <set> #include <vector> #include <map> #define sqr(x) ((x)*(x)) #define PR pair<int,int> #define MP make_pair #define fi first #define se second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long const ll INF = (1ULL<<63)-1; const int inf=0x3f3f3f3f; const int M=100010; const int N=200010; const ll MOD=1000000007; const double eps=1e-3; const double pi=acos(-1.0); using namespace std; vector<int> g[N],gc[N];//g是原图，gc是缩点后的图 int n,u,v,ans,cnt; int vis[N],col[N],comp[N],dp[N];//dp储存该点到图的任意一点的最远距离，comp是该点属于缩点后的图的哪一点 void dfs(int u,int c,int rt) //缩点操作 { if(vis[u]||col[u]!=c) return; vis[u]=1; comp[u]=rt; for(int i=0;i<g[u].size();i++) { int v=g[u][i]; dfs(v,c,rt); } } void DFS(int u,int fa) { int mx=0,mmx=0;//mx是点到图的任意一点的最远距离，mmx是次远距离 for(int i=0;i<gc[u].size();i++) { int v=gc[u][i]; if(v==fa) continue;//防止遍历回父节点 DFS(v,u); mmx=max(mmx,dp[v]+1); if(mmx>mx) swap(mmx,mx); } dp[u]=mx; ans=max(ans,mx+mmx);//图的直径等于某个点的最远距离加上次远距离 } int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&col[i]); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); g[u].push_back(v);g[v].push_back(u); } for(i=1;i<=n;i++) { if(vis[i]==0) dfs(i,col[i],++cnt); } for(i=1;i<=n;i++) { for(j=0;j<g[i].size();j++) { int v=g[i][j]; if(comp[v]!=comp[i]) gc[comp[i]].push_back(comp[v]); } } DFS(1,-1); printf("%d\n",ans); }