1 条题解

  • 1
    @ 2023-8-22 12:16:39

    我们可以建立一棵虚树,

    然后进行树形 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
    上传者