这个题的题意还是很劲的。搞了好久才知道是怎么变得。
（假设已经缩好了点，每次边中间颜色不同的，然后和就和他外面的相同，继续再变这个大的，依次类推，最多就是树的直径D/2）
（还是英语水平太弱了（吐槽++，数学考得还没英语高，还是找个地方撞死吧2333））
1 #include<bits/stdc++.h> 2 #define lowbit(x) x&(-x) 3 #define LL long long 4 #define N 200005 5 #define M 1000005 6 #define mod 1000000007LL 7 #define inf 0x7ffffffff 8 using namespace std; 9 inline int ra() 10 { 11 int x=0,f=1; char ch=getchar(); 12 while (ch<'0' || ch>'9'){if (ch=='-') f=-1; ch=getchar();} 13 while (ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();} 14 return x*f; 15 } 16 struct node{ 17 int next,to; 18 }re[N<<1],e[N<<1]; 19 int head[N],hd[N],cnt,recnt; 20 void insert(int x, int y) 21 { 22 e[++cnt].to=y; 23 e[cnt].next=head[x]; 24 head[x]=cnt; 25 } 26 void reinsert(int x, int y) 27 { 28 re[++recnt].to=y; 29 re[recnt].next=hd[x]; 30 hd[x]=recnt; 31 } 32 int ans,sum[N],belong[N],mx[N],sec[N],n,deep[N]; 33 bool col[N]; 34 void dfs(int x, int num) 35 { 36 belong[x]=num; 37 for (int i=head[x];i;i=e[i].next) 38 { 39 if (belong[e[i].to]) continue; 40 if (col[e[i].to]==col[x]) dfs(e[i].to,num); 41 } 42 } 43 void rebuild() 44 { 45 for (int i=1; i<=n; i++) 46 { 47 for (int j=head[i];j;j=e[j].next) 48 { 49 if (belong[e[j].to]==belong[i]) continue; 50 reinsert(belong[i],belong[e[j].to]); 51 } 52 } 53 } 54 void dfs1(int x, int fa) 55 { 56 deep[x]=1; int mx=0,sc=0; 57 for (int i=hd[x];i;i=re[i].next) 58 { 59 if (re[i].to==fa) continue; 60 dfs1(re[i].to,x); 61 deep[x]=max(deep[x],deep[re[i].to]+1); 62 if (mx==deep[re[i].to]) sc=mx; 63 if (mx<deep[re[i].to]) sc=mx,mx=deep[re[i].to]; 64 if (mx>deep[re[i].to]) sc=max(sc,deep[re[i].to]); 65 } 66 ans=max(ans,max(deep[x],mx+sc+1)); 67 } 68 int main() 69 { 70 n=ra(); 71 for (int i=1; i<=n; i++) col[i]=ra(); 72 for (int i=1; i<n; i++) 73 { 74 int x=ra(),y=ra(); 75 insert(x,y); 76 insert(y,x); 77 } 78 int tot=0; 79 for (int i=1; i<=n; i++) 80 if (!belong[i]) dfs(i,++tot); 81 rebuild(); 82 dfs1(1,0); 83 cout<<ans/2; 84 return 0; 85 } //一开始没看懂题意2333，以为好水 86 /*#include<bits/stdc++.h> 87 #define lowbit(x) x&(-x) 88 #define LL long long 89 #define N 200005 90 #define M 1000005 91 #define mod 1000000007LL 92 #define inf 0x7ffffffff 93 using namespace std; 94 inline int ra() 95 { 96 int x=0,f=1; char ch=getchar(); 97 while (ch<'0' || ch>'9'){if (ch=='-') f=-1; ch=getchar();} 98 while (ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();} 99 return x*f; 100 } 101 struct node{ 102 int next,to; 103 }e[N<<1]; 104 int head[N],cnt; 105 bool vis[N],col[N]; 106 inline void insert(int x, int y) 107 { 108 e[++cnt].to=y; 109 e[cnt].next=head[x]; 110 head[x]=cnt; 111 } 112 void dfs(int x, int fa) 113 { 114 vis[x]=1; 115 for (int i=head[x];i;i=e[i].next) 116 { 117 if (e[i].to==fa || col[e[i].to]!=col[x] || vis[e[i].to]) continue; 118 dfs(e[i].to,x); 119 } 120 } 121 int n,ans1,ans0; 122 int main() 123 { 124 n=ra(); 125 for (int i=1; i<=n; i++) col[i]=ra(); 126 for (int i=1; i<n; i++) 127 { 128 int x=ra(),y=ra(); 129 insert(x,y); 130 insert(y,x); 131 } 132 for (int i=1; i<=n; i++) 133 if (col[i]==0 && !vis[i]) ++ans0,dfs(i,0); 134 memset(vis,0,sizeof(vis)); 135 for (int i=1; i<=n; i++) 136 if (col[i]==1 && !vis[i]) ++ans1,dfs(i,0); 137 cout<<min(ans1,ans0); 138 return 0; 139 }*/