题目大意：在一棵树上，每个节点会被最近的一个关键点管辖，如果同时到多个关键点距离都最小，会被标号最小的那个关键点管辖，每次询问 k 个关键点，输出每个关键点的管辖的结点数量。

$N \leq 300000，q \leq 300000，\sum_{i = 1}^qm_i \leq 300000$

---

题解：参考 https://www.cnblogs.com/zj75211/p/8552270.html

看到 $\sum_{i = 1}^qm_i \leq300000$ 就要想到上虚树了。先将关键点提出来建立一棵虚树。这时不在虚树上的点会被省略，这些点通常在虚树的边上（以及结点上）

虚树上的每一条边的上点（指包括不在虚树上的点），最多只会被两个不同的关键点管辖，且一定有交接的边界。如果知道每条边的端点被哪个结点管辖，可以通过倍增的方法（本质就是二分）找到那个边界，这样就可以求得这些点对管辖点的贡献。

首先要处理的是虚树上每一个点被哪一个点管辖，设 $bel[x]$ 表示管辖 x 的点。可以通过两遍 dfs 来实现，第一遍得到每个点被其子树中距离最近的关键点管辖，第二遍比较来自父亲和兄弟的关键点，取最近的关键点作为 $bel[x]$。

处理完后遍历虚树上的每条边，有两种情况：

1.端点都被同一个点管辖，那么这条边上的点一定也被同一个点管辖，端点上的不在虚树上的结点也会被这个点管辖，这部分贡献可以在遍历的时候处理。

2.端点被不同的点管辖，可以通过倍增找到在这条边上的分界点，同时更新两个关键点的贡献

---

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int n,m,k;
int head[maxn],to[maxn << 1],nxt[maxn << 1],sz;
vector<int> h[maxn];
int p[maxn][22],dep[maxn],siz[maxn];				//倍增以及预处理 
int dfn[maxn],cnt,sta[maxn],top,a[maxn],b[maxn];			//虚树的建立 
int bel[maxn],is[maxn];								//计算每个点被哪个点控制 
int ans[maxn];										//统计答案 
inline int read()
{int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f;
}
void add(int u,int v) {to[sz] = v;nxt[sz] = head[u];head[u] = sz++;
}
void prework(int u,int fa) {if(u == 1) dep[u] = 1;siz[u] = 1,dfn[u] = ++cnt;for(int i = 1; i <= 18; i++)p[u][i] = p[p[u][i - 1]][i - 1];for(int i = head[u]; i + 1; i = nxt[i]) {int it = to[i];if(it == fa) continue;p[it][0] = u;dep[it] = dep[u] + 1;prework(it,u);siz[u] += siz[it];}
}
inline int getlca(int x,int y) {if(dep[x] < dep[y]) swap(x,y);for(int i = 18; i >= 0; i--) {if(dep[p[x][i]] >= dep[y])x = p[x][i];}if(x == y) return x;for(int i = 18; i >= 0; i--) {if(p[x][i] != p[y][i])x = p[x][i],y = p[y][i];}return p[x][0];
}
int dis(int x,int y) {int lca = getlca(x,y);return dep[x] + dep[y] - 2 * dep[lca];
}
inline bool cmp(int a,int b) {return dfn[a] < dfn[b];
}
inline void insert(int x) {int lca = getlca(x,sta[top]);while(top > 1 && dfn[sta[top - 1]] >= dfn[lca]) h[sta[top - 1]].push_back(sta[top]),top--;if(sta[top] != lca) {h[lca].push_back(sta[top]);sta[top] = lca;}sta[++top] = x;
}
void dfs1(int u) {ans[u] = bel[u] = 0;									//清空 if(is[u]) bel[u] = u;for(auto it : h[u]) {dfs1(it);if(!bel[u]) bel[u] = bel[it];else {if(dep[bel[it]] < dep[bel[u]]) bel[u] = bel[it];					//以更近的为管辖点 else if(dep[bel[it]] == dep[bel[u]] && bel[it] < bel[u]) bel[u] = bel[it];	//如果距离相同，以标号更小的为管辖点 }}is[u] = 0;
}
void dfs2(int u) {for(auto it : h[u]) {int d1 = dis(bel[u],it),d2 = dis(bel[it],it);if(d1 < d2) bel[it] = bel[u];else if(d1 == d2 && bel[u] < bel[it]) bel[it] = bel[u];dfs2(it);}
}
void dp(int u) {int sum = siz[u];for(auto it : h[u]) {dp(it);int kp = it;for(int i = 18; i >= 0; i--)				//找到离 u 最近的一个点 if(dep[p[kp][i]] > dep[u])kp = p[kp][i];sum -= siz[kp];if(bel[u] == bel[it]) {							//都被同一个点管辖 ans[bel[u]] += siz[kp] - siz[it];} else {int tp = it;for(int i = 18; i >= 0; i--) {if(dep[p[tp][i]] <= dep[u]) continue;int d1 = dis(p[tp][i],bel[it]),d2 = dis(p[tp][i],bel[u]);if(d1 < d2) tp = p[tp][i];else if(d1 == d2 && bel[it] < bel[u])  tp = p[tp][i];}ans[bel[it]] += siz[tp] - siz[it];ans[bel[u]] += siz[kp] - siz[tp];}}ans[bel[u]] += sum;h[u].clear();
}
int main() {memset(head,-1,sizeof head);n = read();for(int i = 1,u,v; i < n; i++) {u = read(); v = read();add(u,v);add(v,u);}prework(1,0);										//预处理 m = read();while(m--) {k = read();for(int i = 1; i <= k; i++)a[i] = read(),b[i] = a[i],is[a[i]] = 1;sort(a + 1,a + k + 1,cmp);sta[top = 1] = 1;for(int i = a[1] == 1 ? 2 : 1; i <= k; i++)						//建立虚树 insert(a[i]);for(int i = 1; i < top; i++)h[sta[i]].push_back(sta[i + 1]);dfs1(1);dfs2(1);dp(1);for(int i = 1; i <= k; i++)printf("%d%s",ans[b[i]],i == k ? "\n" : " ");}return 0;
}