嘟嘟嘟
突然感觉虚树挺有意思的。
不过对于虚树的构建方法，我只是大概懂了，有些细节还是不清楚，所以现在算是半背着写吧。
对于这道题，我们构建完虚树后（我是真的建出来了，没有用什么dfs序的性质），首先要求出来的是虚树上的点都被哪些点控制，毕竟虚树上不是所有点都是关键点，有些是他们的lca。
因为有些节点可能被他们的兄弟节点控制，所以我们两遍dfs，第一遍考虑这个点能被子树内的哪一个点控制，第二遍考虑能被子树外的哪一个点控制。这个很好写，记录一个到关键点的距离dis，如果有更小的就更新。
对于虚树上的一条边，在原树上可能是一条带有很多叉的链，但那些叉不重要，关键是在原树上找到一个分界点，使这个点到链的低端归儿子管，这个点的父亲到链的顶端归父亲管，然后通过子树大小加加减减就能把那些树叉也算上了。
具体怎么做呢？首先求出控制儿子的关键点(bel[v])和父亲的关键点(bel[u])之间的距离(d)，然后从(bel[v])往上跳(frac{d}{2})步就到了分界点了。但是这个点可能到两个关键点的距离相同，这时候这个点应该归关键点较小的那个点管。因为往下走不知道走哪一个子树，所以写的时候我们往上跳(lfloor frac{d -1}{2}
floor)步，然后再决定是否再往上跳一步。
跳的时候当然要倍增了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 3e5 + 5;
const int N = 19;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, K;
struct Edge
{
int nxt, to, w;
}e1[maxn << 1], e2[maxn << 1];
int head1[maxn], head2[maxn], ecnt1 = -1, ecnt2 = -1;
In void addEdge1(int x, int y, int w)
{
e1[++ecnt1] = (Edge){head1[x], y, w};
head1[x] = ecnt1;
}
In void addEdge2(int x, int y, int w)
{
e2[++ecnt2] = (Edge){head2[x], y, w};
head2[x] = ecnt2;
}
int siz[maxn], dep[maxn], fa[N + 2][maxn], dfsx[maxn], cnt = 0;
In void dfs(int now, int _f)
{
siz[now] = 1, dfsx[now] = ++cnt;
for(int i = 1; (1 << i) <= dep[now]; ++i)
fa[i][now] = fa[i - 1][fa[i - 1][now]];
for(int i = head1[now], v; ~i; i = e1[i].nxt)
{
if((v = e1[i].to) == _f) continue;
dep[v] = dep[now] + 1;
fa[0][v] = now;
dfs(v, now);
siz[now] += siz[v];
}
}
In int lca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int i = N; i >= 0; --i)
if(dep[x] - (1 << i) >= dep[y]) x = fa[i][x];
if(x == y) return x;
for(int i = N; i >= 0; --i)
if(fa[i][x] ^ fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
int vir[maxn], num[maxn];
In bool cmp(int a, int b) {return dfsx[a] < dfsx[b];}
int st[maxn], top = 0;
In void build()
{
sort(vir + 1, vir + K + 1, cmp), st[top = 1] = 1;
for(int i = 1; i <= K; ++i)
{
if(vir[i] == 1) continue;
int Lca = lca(st[top], vir[i]);
while(top > 1 && dep[st[top - 1]] > dep[Lca])
{
int dis = dep[st[top]] - dep[st[top - 1]];
addEdge2(st[top], st[top - 1], dis), addEdge2(st[top - 1], st[top], dis);
--top;
}
if(dep[Lca] < dep[st[top]])
{
int dis = dep[st[top]] - dep[Lca];
addEdge2(st[top], Lca, dis), addEdge2(Lca, st[top], dis);
--top;
}
if(dep[Lca] > dep[st[top]]) st[++top] = Lca;
st[++top] = vir[i];
}
while(top > 1)
{
int dis = dep[st[top]] - dep[st[top - 1]];
addEdge2(st[top], st[top - 1], dis), addEdge2(st[top - 1], st[top], dis);
--top;
}
}
In int jump(int x, int k)
{
for(int i = N; i >= 0; --i) if((k >> i) & 1) x = fa[i][x];
return x;
}
bool vis[maxn];
int Siz[maxn], bel[maxn], dis[maxn], con[maxn];
In void dfs1(int now, int _f) //看自己能被哪一个儿子控制
{
st[++top] = now, Siz[now] = siz[now];
if(vis[now]) dis[now] = 0, bel[now] = now;
else dis[now] = INF;
for(int i = head2[now], v; ~i; i = e2[i].nxt)
{
if((v = e2[i].to) == _f) continue;
dfs1(v, now);
if(dis[now] > dis[v] + e2[i].w || (dis[now] == dis[v] + e2[i].w && bel[v] < bel[now]))
{
dis[now] = dis[v] + e2[i].w;
bel[now] = bel[v];
}
}
}
In void dfs2(int now, int _f)
{
for(int i = head2[now], v; ~i; i = e2[i].nxt)
{
if((v = e2[i].to) == _f) continue;
if(dis[now] + e2[i].w < dis[v] || (dis[now] + e2[i].w == dis[v] && bel[now] < bel[v]))
{ //看自己能否被子树外的某一个点控制
dis[v] = dis[now] + e2[i].w;
bel[v] = bel[now];
}
dfs2(v, now);
if(bel[v] == bel[now]) Siz[now] -= siz[v];
else
{
int d = dis[v] + dis[now] + dep[v] - dep[now] - 1;
int cur = jump(bel[v], d >> 1);
if((d & 1) && bel[now] > bel[v]) cur = fa[0][cur];
Siz[v] += siz[cur] - siz[v], Siz[now] -= siz[cur];
}
con[bel[v]] += Siz[v];
}
if(now == 1) con[bel[now]] += Siz[now];
}
In void init()
{
ecnt2 = -1;
while(top)
{
head2[st[top]] = -1;
con[st[top]] = Siz[st[top]] = bel[st[top]] = dis[st[top]] = vis[st[top]] = 0;
--top;
}
}
int main()
{
//freopen("ha.in", "r", stdin);
//freopen("ha.out", "w", stdout);
Mem(head1, -1), Mem(head2, -1);
n = read();
for(int i = 1; i < n; ++i)
{
int x = read(), y = read();
addEdge1(x, y, 1), addEdge1(y, x, 1);
}
dfs(1, 0);
m = read();
for(int i = 1; i <= m; ++i)
{
K = read();
for(int j = 1; j <= K; ++j) vir[j] = read(), num[j] = vir[j], vis[vir[j]] = 1;
build(); top = 0;
dfs1(1, 0), dfs2(1, 0);
for(int j = 1; j <= K; ++j) write(con[num[j]]), space; enter;
init();
}
return 0;
}
/*
10
1 2
2 4
4 5
5 6
4 7
2 8
8 9
8 10
1 3
1
4
7 9 10 3
*/