树基础

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace TreeBasic
{
    int n;
    vector<int> G[MAX];

    int dep[MAX],dps;
    void Diameter(int now,int father)
    {
        dep[now]=dep[father]+1;
        if(dep[now]>dep[dps]) dps=now;
        for(auto to:G[now]) if(to!=father) Diameter(to,now);
    }
    inline int Diameter() {Diameter(1,0),Diameter(dps,0); return dep[dps];}

    int siz[MAX],wgt[MAX],ctr[2];
    void Centroid(int now,int father)
    {
        siz[now]=1,wgt[now]=0;
        for(auto to:G[now]) if(to!=father) Centroid(to,now),siz[now]+=siz[to],cmax(wgt[now],siz[to]);
        cmax(wgt[now],n-wgt[now]);
        if(wgt[now]<=n/2) ctr[ctr[0]!=0]=now;
    }
    inline void Centroid() {Centroid(1,0);}
}