1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
| #include "ybwhead/ios.h"
const int N = 3e5 + 10, INF = 1e9 + 10;
int n, m, top, cnt;
int dep[N], f[N][20], dfn[N], size[N], lg2[N], sta[N], pnt[N], vis[N], g[N], dp[N], ans[N], tmp[N];
struct graph
{
int tot;
int fir[N], to[2 * N], nxt[2 * N];
graph()
{
tot = 0;
memset(fir, 0, sizeof(fir));
}
inline void add(int x, int y)
{
to[++tot] = y;
nxt[tot] = fir[x];
fir[x] = tot;
to[++tot] = x;
nxt[tot] = fir[y];
fir[y] = tot;
}
} e1, e2;
inline void dfs(int p) //预处理dfn,dep,size
{
dfn[p] = ++cnt, size[p] = 1;
for (register int i = e1.fir[p]; i; i = e1.nxt[i])
{
int q = e1.to[i];
if (q == f[p][0])
continue;
dep[q] = dep[p] + 1, f[q][0] = p;
for (register int j = 1; j <= lg2[dep[q]] + 1; j++)
f[q][j] = f[f[q][j - 1]][j - 1];
dfs(q);
size[p] += size[q];
}
}
inline int get_lca(int x, int y) //找lca
{
if (dep[x] < dep[y])
swap(x, y);
for (register int i = lg2[dep[x]]; i >= 0; i--)
if (dep[f[x][i]] >= dep[y])
x = f[x][i];
if (x == y)
return x;
for (register int i = lg2[dep[x]]; i >= 0; i--)
if (f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
inline bool cmp(int a, int b)
{
return dfn[a] < dfn[b];
}
inline void build(int p) //建立虚树
{
if (top == 0)
{
sta[top = 1] = p;
return;
}
int lca = get_lca(sta[top], p);
while (top > 1 && dep[lca] < dep[sta[top - 1]])
e2.add(sta[top - 1], sta[top]), top--;
if (dep[lca] < dep[sta[top]])
e2.add(lca, sta[top--]);
if (top == 0 || sta[top] != lca)
sta[++top] = lca;
sta[++top] = p;
}
inline void cal(int x, int y)
{
int p = y, q = y;
for (register int i = lg2[dep[p]]; i >= 0; i--)
if (dep[f[p][i]] > dep[x])
p = f[p][i];
ans[g[x]] -= size[p]; //跳到y在原树上对应的x的儿子
for (register int i = lg2[dep[q]]; i >= 0; i--)
{
int llen = dep[y] - dep[f[q][i]] + dp[y], rlen = dep[f[q][i]] - dep[x] + dp[x];
if (dep[f[q][i]] > dep[x] && (llen < rlen || (llen == rlen && g[y] < g[x])))
q = f[q][i]; //倍增找到分割点
}
ans[g[y]] += size[q] - size[y], ans[g[x]] += size[p] - size[q]; //注意这里要加的是size，因为虚树路径上会有子树
}
inline void dfs1(int p, int fa)
{
dp[p] = INF;
for (register int i = e2.fir[p]; i; i = e2.nxt[i])
{
int q = e2.to[i];
if (q == fa)
continue;
dfs1(q, p);
int dis = dep[q] - dep[p]; //注意这里，虚树上的节点并不是连续的
if (dp[q] + dis < dp[p])
dp[p] = dp[q] + dis, g[p] = g[q];
else if (dp[q] + dis == dp[p])
g[p] = min(g[p], g[q]);
}
if (vis[p])
dp[p] = 0, g[p] = p;
}
inline void dfs2(int p, int fa)
{
for (register int i = e2.fir[p]; i; i = e2.nxt[i])
{
int q = e2.to[i];
if (q == fa)
continue;
int dis = dep[q] - dep[p];
if (dp[p] + dis < dp[q])
dp[q] = dp[p] + dis, g[q] = g[p];
else if (dp[p] + dis == dp[q])
g[q] = min(g[q], g[p]);
cal(p, q);
dfs2(q, p);
}
ans[g[p]] += size[p]; //注意这里，还要加上自己
vis[p] = e2.fir[p] = 0;
}
int main()
{
lg2[1] = 0;
for (register int i = 1; i <= 3e5; i++)
lg2[i] = lg2[i >> 1] + 1;
int a, b, T;
yin >> n;
for (register int i = 1; i < n; i++)
{
yin >> a >> b;
e1.add(a, b);
}
dep[1] = 1, dfs(1);
yin >> T;
while (T--)
{
int flag = 1;
top = e2.tot = 0;
yin >> m;
for (register int i = 1; i <= m; i++)
yin >> pnt[i], vis[pnt[i]] = 1, ans[pnt[i]] = 0;
if (!vis[1])
pnt[++m] = 1, flag = 0;
for (register int i = 1; i <= m; i++)
tmp[i] = pnt[i];
sort(pnt + 1, pnt + m + 1, cmp);
for (register int i = 1; i <= m; i++)
build(pnt[i]);
if (top)
while (--top)
e2.add(sta[top], sta[top + 1]);
dfs1(1, 0), dfs2(1, 0);
for (register int i = 1; i <= m; i++)
if (tmp[i] != 1 || flag)
yout << ans[tmp[i]] << " ";
yout << endl;
}
return 0;
}
|