1 条题解
-
1
我们可以建立一棵虚树,
然后进行树形 DP 即可。
// Problem: Kingdom and its Cities // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF613D // Memory Limit: 250 MB // Time Limit: 2000 ms #include <bits/stdc++.h> using namespace std; const int N = 100010, M = 200010; struct edge { int to, next; } e[M]; int head[N], idx = 1; void add(int u, int v) { idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx; } int fa[N][25]; int dep[N]; int dfn[N], tot; int n; void initgraph() { memset(head, 0, sizeof(int) * (n + 10)); idx = 1; } void dfs(int u, int f) { fa[u][0] = f; dep[u] = dep[f] + 1; dfn[u] = ++tot; for (int i = head[u]; i; i = e[i].next) { int to = e[i].to; if (to == f) continue; dfs(to, u); } } void initfa() { for (int j = 1; j < 25; j++) { for (int i = 1; i <= n; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; } } } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int j = 24; j >= 0; j--) { if (dep[fa[u][j]] >= dep[v]) { u = fa[u][j]; } } if (u == v) return u; for (int j = 24; j >= 0; j--) { if (fa[u][j] != fa[v][j]) { u = fa[u][j]; v = fa[v][j]; } } return fa[u][0]; } int a[N], cnt; int sz[N]; int ans; int stk[N], top; void buildgraph() { sort(a + 1, a + cnt + 1, [](const int x, const int y) { return dfn[x] < dfn[y]; }); top = 0; stk[++top] = 1; if (a[1] != 1) stk[++top] = a[1]; for (int i = 2; i <= cnt; i++) { int l = lca(stk[top], a[i]); while (top > 1 && dep[stk[top - 1]] >= dep[l]) { add(stk[top - 1], stk[top]); top--; } if (stk[top] != l) { add(l, stk[top]); stk[top] = l; } stk[++top] = a[i]; } while (top > 1) { add(stk[top - 1], stk[top]); top--; } } void dp(int u) { if (sz[u]) { for (int i = head[u]; i; i = e[i].next) { int to = e[i].to; dp(to); if (sz[to]) ans++; } } else { for (int i = head[u]; i; i = e[i].next) { int to = e[i].to; dp(to); sz[u] += sz[to]; } if (sz[u] > 1) { ans++; sz[u] = 0; } } } void solve() { memset(sz, 0, sizeof(int) * (n + 10)); cin >> cnt; for (int i = 1; i <= cnt; i++) { cin >> a[i]; sz[a[i]] = 1; } for (int i = 1; i <= cnt; i++) { if (sz[fa[a[i]][0]]) { cout << -1 << '\n'; return; } } initgraph(); buildgraph(); ans = 0; dp(1); cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; add(u, v), add(v, u); } dfs(1, 0); initfa(); int T; cin >> T; while (T--) solve(); return 0; }
- 1
信息
- ID
- 4483
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 2
- 上传者