题意
你有一颗 个节点的有根树 (以 号节点为根) ,求最少加入多少条边之后使得根节点(即 11 号节点)到这棵树上任意一点的距离不大于 。
分析
我们考虑覆盖一个节点有多少种方法。
- 在父亲节点连一条边。
- 在儿子节点上连一条边。
- 在当前节点上连一条边。
这样我们发现并不是很好做,考虑叶子节点。叶子节点只有两种可能,在自己或者在父亲上连一条边。那么我们很容易发现。在父亲处连边一定不劣于在当前节点建边。那么依次递归叶子节点就可以了,这样维护叶子节点通过 深度来维护。
代码
#include<bits/stdc++.h> using namespace std; int read() {int x;scanf("%d",&x);return x;} const int N = 2e5 + 100; struct Edge {int to,nxt;}e[N << 1]; #define pii pair<int,int> pii A[N];// first -> dep , second -> id; priority_queue<pii> Q; int dis[N],fa[N],n,head[N],ecnt = 0; void dfs(int x,int F,int D) { fa[x] = F;dis[x] = D;Q.push(pii(dis[x],x)); for(int i = head[x];i;i = e[i].nxt) if(e[i].to ^ fa[x]) dfs(e[i].to,x,D + 1); } int main() { n = read(); for(int i = 1,a,b;i < n;i++) { a = read();b = read(); e[++ecnt] = (Edge){b,head[a]};head[a] = ecnt; e[++ecnt] = (Edge){a,head[b]};head[b] = ecnt; } dfs(1,0,0);int ans = 0; while(Q.size()) { int x = Q.top().second;Q.pop(); if(dis[x] <= 2) continue; dis[fa[x]] = 0;ans++; for(int i = head[fa[x]];i;i = e[i].nxt) dis[e[i].to] = min(dis[e[i].to],1); } cout << ans << endl; return 0; }
分析
对于不太敢相信贪心做法的(大雾)。这题也可以 。考虑 分别表示,当前节点的子树全部覆盖。 表示,自己没有建边,但是儿子覆盖到了自己。 表示当前节点建一条边。 表示,自己不建边,父亲建边。然后树形 扫一次就好了。
代码
#include<bits/stdc++.h> using namespace std; int read() {int x;scanf("%d",&x);return x;} const int N = 2e5 + 100,inf = 0x3f3f3f3f; struct Edge {int to,nxt;}e[N << 1]; #define pii pair<int,int> int n,head[N],ecnt = 0,f[N][3]; void dfs(int x,int F,int dep) { f[x][0] = 0;if(dep < 2)f[x][1] = 0;else f[x][1] = 1;f[x][2] = 0; int res = inf,son = 0; for(int i = head[x];i;i = e[i].nxt) { int y = e[i].to;if(y == F) continue; dfs(y,x,dep + 1); f[x][1] += min(f[y][1],min(f[y][0],f[y][2])); if(f[x][2] < inf) f[x][2] += f[y][0]; if(f[y][1] < f[y][0]) {f[x][0] += f[y][1];son = 1;} else f[x][0] += f[y][0]; res = min(res,f[y][1] - f[y][0]); } if(!son) f[x][0] += res; } int main() { n = read(); for(int i = 1,a,b;i < n;i++) { a = read();b = read(); e[++ecnt] = (Edge){b,head[a]};head[a] = ecnt; e[++ecnt] = (Edge){a,head[b]};head[b] = ecnt; } dfs(1,0,0); cout << min(f[1][1],f[1][0]) << endl; return 0; }