http://codeforces.com/problemset/problem/613/D
題意：
給出n個(gè)點(diǎn)的樹，有q個(gè)詢問，每次詢問給出k個(gè)重要的點(diǎn)，問至少刪掉多少個(gè)非重要的點(diǎn)，使得這個(gè)重要的點(diǎn)都不連通。
?
首先對于一個(gè)詢問，無解的情況肯定是有兩個(gè)相鄰的重要點(diǎn)，直接特判就行。
對于其他情況，進(jìn)行一次tree dp。
如果當(dāng)前點(diǎn)為非重要點(diǎn)，且它的子樹中有至少兩個(gè)重要點(diǎn)，那么將這個(gè)點(diǎn)刪掉。
如果當(dāng)前點(diǎn)為重要點(diǎn)，對于其中一個(gè)兒子，如果這個(gè)兒子的子樹中有重要點(diǎn)，那么將這個(gè)點(diǎn)的兒子刪掉。
但是詢問太多，就要用到虛樹了。
考慮每次詢問，有實(shí)際作用的點(diǎn)只有：重要點(diǎn)以及這些點(diǎn)的lca。那么我們對于每個(gè)詢問，都建一個(gè)新圖，只把這些點(diǎn)抽出來tree dp。
注意在新圖中相鄰的點(diǎn)不一定在原圖中相鄰。
關(guān)于建新圖，當(dāng)我們把倍增lca預(yù)處理好之后，原圖就沒有用了，所以我們把鏈?zhǔn)角跋蛐乔蹇?#xff0c;然后就是普通建圖姿勢了。
/* Footprints In The Blood Soaked Snow */
#include <cstdio>
#include <vector>
#include <algorithm>using namespace std;const int maxn = 100005, maxd = 18, inf = 0x3f3f3f3f;int n, head[maxn], cnt, st[maxn], ed[maxn], depth[maxn], fa[maxn][maxd], clo, sta[maxn], f[maxn][2];
bool imp[maxn];struct _edge {int v, next;
} g[maxn << 1];inline int iread() {int f = 1, x = 0; char ch = getchar();for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';return f * x;
}inline void add(int u, int v) {g[cnt] = (_edge){v, head[u]};head[u] = cnt++;
}inline void dfs(int x) {st[x] = ++clo;for(int i = head[x]; ~i; i = g[i].next) if(g[i].v != fa[x][0]) {fa[g[i].v][0] = x;depth[g[i].v] = depth[x] + 1;dfs(g[i].v);}ed[x] = clo;
}inline int getlca(int u, int v) {if(depth[u] < depth[v]) swap(u, v);for(int i = maxd - 1; i >= 0; i--) if(depth[fa[u][i]] >= depth[v]) u = fa[u][i];for(int i = maxd - 1; i >= 0; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];return u == v ? u : fa[u][0];
}int node[maxn];inline int dp(int x) {int tot = 0, ans = 0;for(int i = head[x]; ~i; i = g[i].next) {ans += dp(g[i].v);tot += node[g[i].v];}if(imp[x]) {ans += tot;node[x] = 1;} else {ans += tot > 1;node[x] = tot == 1;}return ans;
}inline bool cmp(int a, int b) {return st[a] < st[b];
}int main() {n = iread();for(int i = 0; i < maxn; i++) head[i] = -1; cnt = clo = 0;for(int i = 1; i < n; i++) {int x = iread(), y = iread(); x--, y--;add(x, y); add(y, x);}depth[0] = fa[0][0] = 0;dfs(0);for(int j = 1; j < maxd; j++) for(int i = 0; i < n; i++)fa[i][j] = fa[fa[i][j - 1]][j - 1];int T = iread();while(T--) {vector<int> v;int m = iread();for(int i = 0; i < m; i++) {int x = iread(); x--;v.push_back(x);imp[x] = 1;}bool flag = 0;for(int i = 0; i < v.size(); i++)if(fa[v[i]][0] != v[i] && imp[fa[v[i]][0]]) {flag = 1;break;}if(flag) {printf("-1\n");for(int i = 0; i < v.size(); i++) imp[v[i]] = 0;continue;}sort(v.begin(), v.end(), cmp);for(int i = 1; i < m; i++) v.push_back(getlca(v[i - 1], v[i]));sort(v.begin(), v.end(), cmp);v.resize(unique(v.begin(), v.end()) - v.begin());int top = 0; cnt = 0;for(int i = 0; i < v.size(); i++) {int x = v[i]; head[x] = -1;for(; top && !(st[sta[top]] <= st[x] && st[x] <= ed[sta[top]]); top--);if(top) add(sta[top], x);sta[++top] = x;}printf("%d\n", dp(v[0]));for(int i = 0; i < v.size(); i++) imp[v[i]] = 0;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的【Codeforces613D】Kingdom and its Cities【虚树】【Tree DP】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
