Description

世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。

世界树的形态可以用一个数学模型来描述：世界树中有 个种族，种族的编号分别从 到 ，分别生活在编号为 到 的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为 。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地 和 之间有道路， 和 之间有道路，因为每条道路长度为 而且又不可能出现环，所以 与 之间的距离为 。

出于对公平的考虑，第 年，世界树的国王需要授权 个种族的聚居地为临时议事处。对于某个种族 （ 为种族的编号），如果距离该种族最近的临时议事处为 （ 为议事处所在聚居地的编号），则种族 将接受 议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则 为其中编号最小的临时议事处）。

现在国王想知道，在 年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。

Input

第一行为一个正整数 ，表示世界树中种族的个数。
接下来 行，每行两个正整数 ，，表示 聚居地与 聚居地之间有一条长度为 的双向道路。
接下来一行为一个正整数 ，表示国王询问的年数。
接下来 块，每块两行：
第 块的第一行为一个正整数 ，表示第 年授权的临时议事处的个数。
第 块的第二行为 个正整数 ，表示第 年被授权为临时议事处的聚居地编号（保证互不相同）。

Output

输出包含 行，第 行为 个整数，该行的第 个数表示第 年被授权的聚居地 的临时议事处管理的种族个数。

Sample Input

10 
2 1 
3 2 
4 3 
5 4 
6 1 
7 3 
8 3 
9 4 
10 1 
5 
2 
6 1   
5 
2 7 3 6 9   
1 
8  
4 
8 7 10 3   
5 
2 9 3 5 8

Sample Output

1 9   
3 1 4 1 1   
10  
1 1 3 5   
4 1 3 1 1

HINT

对于所有的数据 。

Solution

明确f、ans数组，

表示通过这个点能够控制的点的数量
起始值是 是在虚树上的直接儿子
然后遍历儿子边，找到分界点，上面是由控制，下面到都是由控制。

这是显然的。
最后

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 500000;
int head[N], en;
struct Edge {
    int u, v, nxt;
}e[N * 2];
int n, m, d[N];
void addedge(int x, int y) {
    e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
} 
int dfn[N], num, siz[N];
int f[N][21]; 
void dfs(int x, int F) {
    dfn[x] = ++num;
    d[x] = d[F] + 1;
    f[x][0] = F;
    siz[x] = 1;
    for(int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = head[x]; i;i = e[i].nxt) {
        int y = e[i].v;
        if(y == F) continue;
        dfs(y, x);
        siz[x] += siz[y];
    }
}
int lca(int x, int y) {
    if(d[x] < d[y]) swap(x, y);
    for(int i = 20; ~i; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = 20; ~i; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
int getdis(int x, int y) {
    if(x == 0 || y == 0) return 1e9;
    int z = lca(x, y);
    return d[x] + d[y] - 2 * d[z];
}
int get(int x, int w) {
    for(int i = 0; i <= 20; ++i) if(w & (1 << i)) x = f[x][i];
    return x;
}
int t;
struct Que {
    int x, i;
    bool operator < (const Que &rhs) const {
        return dfn[x] < dfn[rhs.x];
    }
}a[N];
bool v[N];
struct GGG {
    int head[N], en;
    struct Edge {
        int u, v, nxt;
    }e[N * 2];
    int n, m;
    void addedge(int x, int y) {
        e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
    } 
    int top, st[N];
    int f[N], ans[N], bel[N]; 
    void init() {
        st[top = 1] = 1;
        for(int i = 1; i <= en; ++i) head[e[i].u] = 0;
        for(int i = 1; i <= en; ++i) {
            bel[e[i].u] = bel[e[i].v] = 0;
            f[e[i].u] = f[e[i].v] = 0;
            ans[e[i].u] = ans[e[i].v] = 0;
        }
        en = 0;
    } 
    void ins(int x) {
        int p = lca(st[top], x);
        while(top > 1 && d[st[top - 1]] >= d[p]) addedge(st[top - 1], st[top]), --top;
        if(st[top] == p) {
            st[++top] = x;
            return;
        }
        addedge(p, st[top]);
        st[top] = p;
        st[++top] = x;
    } 
    void dfs(int x, int F) {
        if(v[x]) bel[x] = x;
        else bel[x] = bel[F];
        f[x] = siz[x];
        int val1, val2;
        for(int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].v;
            dfs(y, x);
            f[x] -= siz[y]; 
            val1 = getdis(bel[y], x);
            val2 = getdis(bel[x], x);
            if(val1 < val2 || val1 == val2 && bel[y] < bel[x]) bel[x] = bel[y];
        }
    }
    void dfs2(int x, int F) {
        int val1 = getdis(x, bel[x]);
        int val2 = getdis(x, bel[F]);
        if(val1 > val2 || val1 == val2 && bel[F] < bel[x]) bel[x] = bel[F];
        for(int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].v;
            dfs2(y, x);
        }
    }

    void solve(int x, int F) {
        for(int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].v;
            if(y == F) continue;

            int r = d[y] - d[x] + 1, l = 0;
            while(r - l > 1) {
                int mid = (l + r) >> 1;
                int t = get(y, mid);
                int val1 = getdis(t, bel[x]);
                int val2 = getdis(t, bel[y]);
                if(val1 > val2 || val1 == val2 && bel[x] > bel[y]) l = mid;
                else r = mid;
            }
            int z = get(y, l);
            f[x] -= siz[z] - siz[y];
            f[y] += siz[z] - siz[y];
            solve(y, x);
        }
        ans[bel[x]] += f[x]; 
    }

}g;
int ans[N];
int main() {
    n = read();
    for(int i = 1; i < n; ++i) {
        int x = read(), y = read();
        addedge(x, y);
        addedge(y, x);
    }
    dfs(1, 1);
    int Q = read();
    d[0] = 1e7;
    for(int T = 1; T <= Q; ++T) {
        t = read();
        for(int i = 1; i <= t; ++i)
            a[i].x = read(), a[i].i = i;
        sort(a + 1, a +1 + t);
        g.init();
        for(int i = 1; i <= t; ++i) v[a[i].x] = 1;
        for(int i = (a[1].x == 1 ? 2 : 1); i <= t; ++i) g.ins(a[i].x);
        while(g.top > 1) g.addedge(g.st[g.top - 1], g.st[g.top]), g.top--;

        g.dfs(1, 0);
        g.dfs2(1, 0);
        g.solve(1, 0);

        for(int i = 1; i <= t; ++i) {
            ans[a[i].i] = g.ans[a[i].x];
        }
        for(int i = 1; i <= t; ++i) printf("%d ", ans[i]);
        puts("");
        for(int i = 1; i <= t; ++i) v[a[i].x] = 0;
    }
    return 0;
}