题意：
给定一棵树，有两类点，特殊点与普通点，每个点被离他最近的特殊点管理（距离相同以编号最小的为准），有 \(Q\) 个询问，每个询问形如 \(k,s_{1},s_{2},...,s_{k}\)，表示这 \(k\) 个点为特殊点，询问每个特殊点能管理的点的数量。
\(\sum k \le 3 \times 10^5\)。
分析：
考虑暴力，每个点要么被它子树内的点管理，要么被子树外的点管理，跑两遍 DFS 简单dp一下就好了。时间复杂度 \(O(nQ)\)。
显然需要建虚树，对于虚树上的点向暴力做法一样处理就好了。
那不在虚树上的点怎么做呢？可以分成两种：
- 被虚树上的一条边 \(x \rightarrow y\) 夹着的一些点，需要对这些点划分势力，一些属于 \(g_{x}\)，一些属于 \(g_{y}\)。找一个分界线即可。算贡献时需要求 \(k\) 级祖先，最简单的方法是倍增。
- 在虚树上的一个点的一个没有特殊点的子树，这些点全部归属于 \(g_{x}\)，需要注意的是，不能暴力计算，简单容斥一下即可。
细节有点多。时间复杂度 \(O(Q\log n + \sum k \log \sum k)\)。
代码：
#include<bits/stdc++.h>
#define N 300005
#define il inline
using namespace std;
int n, Q, m;
int father[N], dfn[N], siz[N], cnt, son[N], dep[N], top[N], fa[N][20];
vector<int>p[N], G[N]; //p是原来的树,G是虚树
il void dfs(int x, int Fa) {
father[x] = Fa;
fa[x][0] = Fa;
siz[x] = 1;
dfn[x] = ++cnt;
int Maxson = -1;
dep[x] = dep[Fa] + 1;
for(auto y : p[x]) {
if(y == Fa) continue;
dfs(y, x);
siz[x] += siz[y];
if(Maxson < siz[y]) {
Maxson = siz[y];
son[x] = y;
}
}
}
il void dfs2(int x, int topf) {
top[x] = topf;
if(!son[x]) return;
dfs2(son[x], topf);
for(auto y : p[x]) {
if(top[y]) continue;
dfs2(y, y);
}
}
il int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = father[top[x]];
}
if(dep[x] < dep[y]) return x;
else return y;
}
int h[N], tot, z[N], ans[N], f[N], g[N]; //f[i]表示离TA最近的议事处的距离,g[i]表示离TA最近的议事处
bool vis[N]; //是否为议事处
il bool cmp(int a, int b) {
return dfn[a] < dfn[b];
}
il void dp1(int x) { //求出在x子树内最近的议事处
if(vis[x]) f[x] = 0, g[x] = x;
for(auto y : G[x]) {
dp1(y);
if(f[y] + (dep[y] - dep[x]) < f[x]) f[x] = f[y] + (dep[y] - dep[x]), g[x] = g[y];
else if(f[y] + (dep[y] - dep[x]) == f[x]) g[x] = min(g[x], g[y]);
}
}
il void dp2(int x) { //求出在x子树外最近的议事处
for(auto y : G[x]) {
if(f[x] + (dep[y] - dep[x]) < f[y]) f[y] = f[x] + (dep[y] - dep[x]), g[y] = g[x];
else if(f[x] + (dep[y] - dep[x]) == f[y]) g[y] = min(g[y], g[x]);
dp2(y);
}
}
il int Get_kth(int x, int k) {
for(int i = 18; i >= 0; i--)
if(k >= (1 << i)) x = fa[x][i], k -= (1 << i);
return x;
}
il void Get(int x) {
int res = siz[x] - 1;
for(auto y : G[x]) {
int d = dep[y] - dep[x];
if(d - 1 > 0) { //x,y之间有点
int X = (f[x] + d - f[y]) / 2;
X = max(X, 0);
if(X > 0 && f[y] + X == f[x] + d - X && g[x] < g[y]) X--;
if(X == d) X--;
if(X > 0) ans[g[y]] += siz[Get_kth(y, X)] - siz[y];
if(d - 1 - X > 0) ans[g[x]] += siz[Get_kth(y, d - 1)] - siz[Get_kth(y, X)];
}
int num = Get_kth(y, d - 1);
res -= siz[num];
Get(y);
}
ans[g[x]] += res;
}
int uu[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 1);
for(int j = 1; j <= 18; j++)
for(int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
cin >> Q;
while(Q--) {
cin >> m;
for(int i = 1, x; i <= m; i++) {
cin >> h[i];
uu[i] = h[i];
vis[h[i]] = 1;
ans[h[i]] = 0;
}
h[++m] = 1;
sort(h + 1, h + m + 1, cmp);
tot = 0;
for(int i = 1; i <= m - 1; i++) z[++tot] = h[i], z[++tot] = lca(h[i], h[i + 1]);
z[++tot] = h[m];
sort(z + 1, z + tot + 1, cmp);
tot = unique(z + 1, z + tot + 1) - z - 1;
for(int i = 1; i <= tot; i++) G[z[i]].clear(), f[z[i]] = g[z[i]] = 1e9;
for(int i = 1; i < tot; i++) G[lca(z[i], z[i + 1])].push_back(z[i + 1]);
dp1(1); dp2(1);
for(int i = 1; i <= tot; i++) ans[g[z[i]]]++;
Get(1);
for(int i = 1; i <= m - 1; i++) cout << ans[uu[i]] << " ", vis[uu[i]] = 0;
cout << endl;
}
return 0;
}