//点和线段树都从1开始

//边使用vector

vector<int> G[maxn];

int dfs_clock,que[maxn*],num[maxn],iii[maxn],b[maxn],a[maxn],top[maxn],deep[maxn],fa[maxn],idx[maxn];

//采用静态链表

//a[i]   是初始时树上每个点的权值

//b[i]   是经过bfs后每个点的权值

//idx[i] 是每个点在全局线段树中的下标

void build_List()

{

    int ft = , rear = ;

    que[rear++] = ;

    fa[] = ;

    deep[] = ;

    while(ft < rear)

    {

        int u = que[ft++];

        for(int i = ; i < G[u].size(); i++)

        {

            int v = G[u][i];

            if(v == fa[u]) continue;

            fa[v] = u;

            que[rear++] = v;

            deep[v] = deep[u]+;

        }

    }

    memset(num, , sizeof num);

    for(int i = n-; i >= ; i--)

    {

        int u = que[i];

        num[u]++;

        num[fa[u]] += num[u];

    }

    for(int i = ; i <= n; i++)

    {

        for(int j = ; j < G[i].size(); j++) if(G[i][j] != fa[i])

                if(G[i][] == fa[i] || num[G[i][j]] > num[G[i][]])

                    swap(G[i][], G[i][j]);

    }

    top[] = ;

    for(int i = ; i < n; i++)

    {

        int u = que[i];

        if(G[fa[u]][] == u) top[u] = top[fa[u]];

        else top[u] = u;

    }

    memset(iii, , sizeof iii);

    ft = ;

    dfs_clock = ;

    que[++ft] = ;

    idx[] = ++dfs_clock;

    b[] = a[];

    while(ft)

    {

        int u = que[ft];

        if(iii[u] >= G[u].size()) ft--;

        else if(G[u][iii[u]] == fa[u]) iii[u]++;

        else

        {

            int v = G[u][iii[u]];

            que[++ft] = v;

            idx[v] = ++dfs_clock;

            b[idx[v]] = a[v];

            iii[u]++;

        }

    }

}