题面
题解
虚树好题
构出虚树后，一定要仔细梳理关键点之间的点是上面属于父亲，下面属于儿子。
然后二分出所有的点的所属就可以了
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(300010);
struct edge { int next, to, dis; } e[maxn << 1];
int head[maxn], e_num, n, q, f[21][maxn], dep[maxn], belong[maxn];
int size[maxn], dfn[maxn], cnt, stk[maxn], top, sur[maxn], dis[maxn];
inline void add_edge(int from, int to, int dis = 1)
{
e[++e_num] = (edge) {head[from], to, dis};
head[from] = e_num;
}
void dfs(int x)
{
dep[x] = dep[f[0][x]] + 1; size[x] = 1;
for(RG int i = 1; i <= 20; i++)
f[i][x] = f[i - 1][f[i - 1][x]];
dfn[x] = ++cnt;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == f[0][x]) continue;
f[0][to] = x; dfs(to); size[x] += size[to];
}
}
int LCA(int a, int b)
{
if(dep[a] < dep[b]) std::swap(a, b);
for(RG int i = 20; ~i; i--) if(dep[f[i][a]] >= dep[b]) a = f[i][a];
if(a == b) return a;
for(RG int i = 20; ~i; i--) if(f[i][a] != f[i][b]) a = f[i][a], b = f[i][b];
return f[0][a];
}
int jump(int x, int k)
{
if(dep[x] < k) return x;
for(RG int i = 20; ~i; i--) if(dep[f[i][x]] >= k) x = f[i][x];
return x;
}
struct node { int x, id; } p[maxn];
inline bool cmpx(const node &lhs, const node &rhs)
{ return dfn[lhs.x] < dfn[rhs.x]; }
inline bool cmpid(const node &lhs, const node &rhs) { return lhs.id < rhs.id; }
int k, vis[maxn], ans[maxn], t[maxn], tot;
void build()
{
std::sort(p + 1, p + k + 1, cmpx);
stk[top = 1] = 1;
for(RG int i = 1; i <= k; i++)
{
int x = p[i].x; if(x == 1) continue;
int lca = LCA(stk[top], x);
while(top > 1 && dep[stk[top - 1]] > dep[lca])
{
int dis = dep[stk[top]] - dep[stk[top - 1]];
add_edge(stk[top], stk[top - 1], dis);
add_edge(stk[top - 1], stk[top], dis);
--top;
}
if(dep[lca] < dep[stk[top]])
{
int dis = dep[stk[top]] - dep[lca];
add_edge(stk[top], lca, dis);
add_edge(lca, stk[top], dis);
--top;
}
if(dep[lca] > dep[stk[top]]) stk[++top] = lca;
stk[++top] = x;
}
while(top > 1)
{
int dis = dep[stk[top]] - dep[stk[top - 1]];
add_edge(stk[top], stk[top - 1], dis);
add_edge(stk[top - 1], stk[top], dis);
--top;
}
}
void dfs1(int x, int fa)
{
sur[x] = size[x]; t[++tot] = x;
if(vis[x]) dis[x] = 0, belong[x] = x;
else dis[x] = 1e9;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa) continue;
dfs1(to, x);
if(dis[x] > dis[to] + e[i].dis ||
(dis[x] == dis[to] + e[i].dis && belong[x] > belong[to]))
dis[x] = dis[to] + e[i].dis, belong[x] = belong[to];
}
}
void dfs2(int x, int fa)
{
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa) continue;
if(dis[to] > dis[x] + e[i].dis ||
(dis[to] == dis[x] + e[i].dis && belong[to] > belong[x]))
dis[to] = dis[x] + e[i].dis, belong[to] = belong[x];
dfs2(to, x);
if(belong[to] == belong[x]) sur[x] -= size[to];
else
{
int d = dis[to] + dis[x] + dep[to] - dep[x] - 1, k = d / 2 - dis[to];
int t = jump(to, dep[to] - k);
if((d & 1) && belong[x] > belong[to] && k >= 0) t = f[0][t];
sur[to] += size[t] - size[to], sur[x] -= size[t];
}
ans[belong[to]] += sur[to];
}
if(x == 1) ans[belong[x]] += sur[x];
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read();
for(RG int i = 1, a, b; i < n; i++)
a = read(), b = read(), add_edge(a, b), add_edge(b, a);
dfs(1); q = read(); clear(head, 0); e_num = 0;
while(q--)
{
k = read();
for(RG int i = 1; i <= k; i++)
vis[(p[i] = (node) {read(), i}).x] = 1;
build(); dfs1(1, 0); dfs2(1, 0);
std::sort(p + 1, p + k + 1, cmpid);
for(RG int i = 1; i <= k; i++) printf("%d ", ans[p[i].x]);
puts(""); e_num = 0;
for(RG int i = 1; i <= tot; i++)
vis[t[i]] = head[t[i]] = ans[t[i]]
= sur[t[i]] = belong[t[i]] = dis[t[i]] = 0;
tot = 0;
}
return 0;
}