请问你编程可以做到多少,可以处理输入输出么?
我先发在这
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2000100;
const int MAX_M = 2000100;
struct Edge{
int v,next;
} E1[MAX_M],E2[MAX_M];
int p1[MAX_N],p2[MAX_N],eid1,eid2;
int c1[MAX_N],c2[MAX_N],cid;
bool vis[MAX_N];
void init() {
memset(p1,-1,sizeof(p1));
memset(p2,-1,sizeof(p2));
eid1 = eid2 = 0;
}
void insert1(int u,int v) {
E1[eid1].v = v;
E1[eid1].next = p1[u];
p1[u] = eid1++;
}
void insert2(int u,int v) {
E2[eid2].v = v;
E2[eid2].next = p2[u];
p2[u] = eid2++;
}
int maxlen,point;
void dfs(int u,int step){
vis[u] = true;
if(step > maxlen){
maxlen = step;
point = u;
}
for(int i = p2[u];i != -1;i = E2[i].next){
if(!vis[E2[i].v]){
dfs(E2[i].v,step + 1);
}
}
}
void zip(int u){
c2[u] = cid;
for(int i = p1[u];i != -1;i = E1[i].next){
if(c1[E1[i].v] == c1[u] && !c2[E1[i].v]) zip(E1[i].v);
}
}
int diameter(){
maxlen = -1;
dfs(1,0);
memset(vis,0,sizeof(vis));
maxlen = -1;
dfs(point,0);
return maxlen;
}
int main(){
int n;
cin >>n;//
init();
for(int i = 1;i <= n;i ++) cin >>c1[i];//
for(int i = 0;i < n - 1;i ++){
int u,v;
cin >> u >> v;
insert1(u,v);
insert1(v,u);
}
for(int i = 1;i <= n;i ++){
if(!c2[i]){
cid ++;
zip(i);
}
}
for(int i = 1;i <= n;i ++){
for(int j = p1[i];j != -1;j = E1[j].next){
if(c2[i] != c2[E1[j].v]){
insert2(c2[i],c2[E1[j].v]);
insert2(c2[E1[j].v],c2[i]);
}
}
}
cout << (diameter() + 1) / 2 << endl;
return 0;
}