The original problem is AIM TECH Round4 div.2 problem E.[844E](http://codeforces.me/problemset/problem/844/E)↵
↵
I read the tutorial and read some book about methods of Finding centroids int a tree,and a friend told me that if a tree have two centroid,then the max size of the subtree of each of these centroids is equal to N/2(N is the number of vertexes in a tree).↵
↵
I wrote this method to find centroid but I got WA on 11,but I wrote the second method to find that I got AC.What's the differences between them?Tell me please,thank you in advance:-)↵
↵
the code I got WA:[submission here,in my another account](http://codeforces.me/contest/844/submission/30092739)↵
↵
~~~~~↵
pair<int ,int > FindCent(int v,int fa,int N)↵
{↵
pair<int ,int > Res=MP(inf,-1);↵
int S=1,maxsiz=0;↵
for(int i=0;i<(int)g[v].size();i++){↵
int u=g[v][i];↵
if(u!=fa){↵
Res=min(Res,FindCent(u,v,N));↵
S+=siz[u];↵
maxsiz=max(maxsiz,siz[u]);↵
}↵
}↵
maxsiz=max(maxsiz,N-S);↵
Res=min(Res,MP(maxsiz,v));↵
return Res;↵
}↵
~~~~~↵
The main idea is to find a vertex that after delete it,the size of the max substree of the whole tree is as small as possible...↵
↵
And the code I got AC:[submission here,also in my another account](http://codeforces.me/contest/844/submission/30092894)↵
↵
~~~~~↵
int Findcent(int v,int fa)↵
{↵
for(int i=0;i<(int)g[v].size();i++){↵
int u=g[v][i];↵
if(u!=fa && siz[u]>n/2) return Findcent(u,v);↵
}↵
return v;↵
}↵
~~~~~↵
I think the main idea is similar but why one got WA and another got AC...? ↵
↵
↵
And ....If you have some good materials(in English or in Chinese please;-) about the centroid of a tree,could you please tell me?Thank you very much......↵
↵
I read the tutorial and read some book about methods of Finding centroids in
↵
I wrote this method to find centroid but I got WA on 11,but I wrote the second method to find that I got AC.What's the differences between them?Tell me please,thank you in advance:-)↵
↵
the code I got WA:[submission here,in my another account](http://codeforces.me/contest/844/submission/30092739)↵
↵
~~~~~↵
pair<int ,int > FindCent(int v,int fa,int N)↵
{↵
pair<int ,int > Res=MP(inf,-1);↵
int S=1,maxsiz=0;↵
for(int i=0;i<(int)g[v].size();i++){↵
int u=g[v][i];↵
if(u!=fa){↵
Res=min(Res,FindCent(u,v,N));↵
S+=siz[u];↵
maxsiz=max(maxsiz,siz[u]);↵
}↵
}↵
maxsiz=max(maxsiz,N-S);↵
Res=min(Res,MP(maxsiz,v));↵
return Res;↵
}↵
~~~~~↵
The main idea is to find a vertex that after delete it,the size of the max substree of the whole tree is as small as possible...↵
↵
And the code I got AC:[submission here,also in my another account](http://codeforces.me/contest/844/submission/30092894)↵
↵
~~~~~↵
int Findcent(int v,int fa)↵
{↵
for(int i=0;i<(int)g[v].size();i++){↵
int u=g[v][i];↵
if(u!=fa && siz[u]>n/2) return Findcent(u,v);↵
}↵
return v;↵
}↵
~~~~~↵
I think the main idea is similar but why one got WA and another got AC...? ↵
↵
↵
And ....If you have some good materials(in English or in Chinese please;-) about the centroid of a tree,could you please tell me?Thank you very much......↵



