题面
洛谷
题解
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 3e5 + 5;
struct Graph { int to, next; } e[MAX_N << 1]; int fir[MAX_N], e_cnt;
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }
void Add_Edge(int u, int v) { e[e_cnt] = (Graph){v, fir[u]}, fir[u] = e_cnt++; }
int bin[20];
int N, M, dfn;
int fa[MAX_N][20], dep[MAX_N], id[MAX_N], size[MAX_N];
int a[MAX_N], b[MAX_N], f[MAX_N];
int top, stk[MAX_N], c[MAX_N];
int rem[MAX_N], bel[MAX_N];
bool cmp(int a, int b) { return id[a] < id[b]; }
void dfs(int x, int f) {
id[x] = ++dfn;
size[x] = 1;
for (int i = 1; bin[i] <= dep[x]; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = fir[x]; ~i; i = e[i].next)
if (e[i].to != f) {
fa[e[i].to][0] = x;
dep[e[i].to] = dep[x] + 1;
dfs(e[i].to, x);
size[x] += size[e[i].to];
}
}
int LCA(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
int t = dep[y] - dep[x];
for (int i = 0; bin[i] <= t; i++)
if (bin[i] & t) y = fa[y][i];
for (int i = 18; i >= 0; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return x == y ? x : fa[x][0];
}
int dis(int a, int b) { return dep[a] + dep[b] - 2 * dep[LCA(a, b)]; }
void solve(int a, int b) {
int x = b, mid = b;
for (int i = 18; i >= 0; i--)
if (dep[fa[x][i]] > dep[a]) x = fa[x][i];
rem[a] -= size[x];
if (bel[a] == bel[b]) {
f[bel[a]] += size[x] - size[b];
return ;
}
for (int i = 18; i >= 0; i--) {
int nxt = fa[mid][i]; if (dep[nxt] <= dep[a]) continue;
int t1 = dis(bel[a], nxt), t2 = dis(bel[b], nxt);
if (t1 > t2 || (t1 == t2 && bel[b] < bel[a])) mid = nxt;
}
f[bel[a]] += size[x] - size[mid];
f[bel[b]] += size[mid] - size[b];
}
void dfs1(int x) {
c[++dfn] = x, rem[x] = size[x];
for (int i = fir[x]; ~i; i = e[i].next) {
dfs1(e[i].to); if (!bel[e[i].to]) continue;
int t1 = dis(bel[e[i].to], x), t2 = dis(bel[x], x);
if ((t1 == t2 && bel[e[i].to] < bel[x]) || t1 < t2 || !bel[x])
bel[x] = bel[e[i].to];
}
}
void dfs2(int x) {
for (int i = fir[x]; ~i; i = e[i].next) {
int t1 = dis(bel[x], e[i].to), t2 = dis(bel[e[i].to], e[i].to);
if ((t1 == t2 && bel[e[i].to] > bel[x]) || t1 < t2 || !bel[e[i].to])
bel[e[i].to] = bel[x];
dfs2(e[i].to);
}
}
void solve() {
top = dfn = e_cnt = 0;
M = gi();
for (int i = 1; i <= M; i++) a[i] = b[i] = gi();
for (int i = 1; i <= M; i++) bel[a[i]] = a[i];
sort(&a[1], &a[M + 1], cmp);
if (bel[1] != 1) stk[++top] = 1;
for (int i = 1; i <= M; i++) {
int t = a[i], f = 0;
while (top > 0) {
f = LCA(stk[top], t);
if (top > 1 && dep[f] < dep[stk[top - 1]])
Add_Edge(stk[top - 1], stk[top]), top--;
else if (dep[f] < dep[stk[top]]) {
Add_Edge(f, stk[top]); top--;
break;
} else break;
}
if (stk[top] != f) stk[++top] = f;
stk[++top] = t;
}
while (top > 1) Add_Edge(stk[top - 1], stk[top]), top--;
dfs1(1), dfs2(1);
for (int i = 1; i <= dfn; i++)
for (int j = fir[c[i]]; ~j; j = e[j].next) solve(c[i], e[j].to);
for (int i = 1; i <= dfn; i++) f[bel[c[i]]] += rem[c[i]];
for (int i = 1; i <= M; i++) printf("%d ", f[b[i]]);
puts("");
for (int i = 1; i <= dfn; i++) f[c[i]] = bel[c[i]] = rem[c[i]] = 0, fir[c[i]] = -1;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
clearGraph();
bin[0] = 1;
for (int i = 1; i < 20; i++) bin[i] = bin[i - 1] << 1;
N = gi();
for (int i = 1; i < N; i++) {
int u = gi(), v = gi();
Add_Edge(u, v);
Add_Edge(v, u);
}
dfs(1, 0);
clearGraph();
int Q = gi();
while (Q--) solve();
return 0;
}