Help about Finding the centroid of a tree...What's the difference between these two methods?
Difference between en1 and en2, changed 1 character(s)
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 in
t 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......↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English -IA- 2017-09-05 14:00:16 744
en2 English -IA- 2017-09-05 10:37:14 1 Tiny change: 'ntroids int a tree,an' -> 'ntroids in a tree,an'
en1 English -IA- 2017-09-05 10:30:53 1866 Initial revision (published)