namespace TreeDiv {
    const int maxn = 100005;
    int n;
    bool cuse[maxn];
    int sz[maxn];
    int ans;
    struct Edge {
        int v,w;
    };
    vector<Edge> g[maxn];
    void init(int _n) {
        n = _n;
        for (int i=0; i<n; ++i)
            g[i].clear(), cuse[i] = 0, sz[i] = 0;
    }
    inline void addEdge(int u, int v, int w) {  //无向边需要add两次
        g[u].push_back((Edge) {
            v,w
        });
    }
    int getSize(int u, int fa) {            //计算各个子树的大小
        sz[u] = 1;
        for (int i=0; i<(int)g[u].size(); ++i) {
            int v = g[u][i].v;
            if (v == fa || cuse[v]) continue;
            sz[u] += getSize(v, u);
        }
        return sz[u];
    }
    pair<int,int> getCentroid(int u, int fa, int cnt) {         //返回一个pair<最大子树的顶点数, 重心顶点编号>
        pair<int,int> res = make_pair(inf, -1);
        int c=1, maxsz=0;
        for (int i=0; i<(int)g[u].size(); ++i) {
            int v = g[u][i].v;
            if (v == fa || cuse[v]) continue;
            res = min(res, getCentroid(v, u, cnt));
            maxsz = max(maxsz, sz[v]), c += sz[v];
        }
        maxsz = max(maxsz, cnt-c);
        res = min(res, make_pair(maxsz, u));
        return res;
    }
    //下面是具体题目的处理
}