Codeforces Round #506 (Div. 3) E. Tree with Small Distances (cf 1029E)

题目：Tree with Small Distances

题意：
给出一棵树，求最少加多少条边，使得$1$号节点到每个节点的距离小于等于$2$。

思路：
比赛时做的人最少的题，赛后写了好久…

↑↑↑QωQ【绝望.jpg】

嗯这题一眼看出来是树形$dp$，实现上不太容易。
刚开始的思路是令$f[x][w]$表示节点$x$的上面的第$w-1$个节点向$1$有连边时，要使$x$向下的子树满足条件时所需的最小连边数量。然后发现父节点到$1$的最短路径中经过了儿子节点的情况不好处理。
换了个思路，令$f[x][w]$表示节点$x$的状态为$w$时，要使$x$向下的子树满足条件时所需的最小连边数量。这里的状态$w$为$0$时，代表$x$由父节点$fa$转移得到；$w$为$1$时，代表$x$由子节点$y$转移得到；$w$为$0$时代表$x$和$1$有连边。
转移方程：
$f[x][0]=∑min(f[y][1],f[y][2]+1)$
$f[x][1]=∑min(f[y][1],f[y][2]+1)+min(f[y][2]+1-min(f[y][2]+1,f[y][1]))$
$f[x][3]=∑min(f[y][0],f[y][1],f[y][2]+1)$
注意$1$号节点和$1$号节点的儿子要单独判断，即$1$号节点的儿子的状态只能为$2$。

给两组数据QωQ~

Input
6
1 2
2 3
3 4
4 5
5 6Output
1Input
11
1 2
2 3
3 4
4 5
5 6
5 7
4 8
8 9
9 10
9 11Output
2

代码：

#include<bits/stdc++.h>
using namespace std;#define ll long long
#define inf (1<<30)
#define maxn 200000int n;
int f[maxn+5][5];
vector<int> a[maxn+5];
int fa[maxn+5];
int d[maxn+5];void read(int& x) {scanf("%d",&x);
}void dfs(int x) {for(int i=0; i<a[x].size(); i++) {int y=a[x][i];if(fa[x]==y) continue;fa[y]=x;d[x]=d[y]+1;dfs(y);}
}int dp(int x,int w) {if(w==1&&a[x].size()==1) return f[x][w]=inf;if(f[x][w]) return f[x][w];int z=inf;for(int i=0;i<a[x].size();i++) {int y=a[x][i];if(y==fa[x]) continue;dp(y,0),dp(y,1),dp(y,2);if(w!=2) f[x][w]+=min(f[y][1],f[y][2]+1);else f[x][w]+=min(min(f[y][0],f[y][1]),f[y][2]+1);z=min(z,f[y][2]+1-min(f[y][2]+1,f[y][1]));}if(w==1) f[x][w]+=z;return f[x][w];
}int main() {read(n);int frt=0;for(int i=1; i<n; i++) {int x,y;read(x);read(y);if(frt==0) frt=x;a[x].push_back(y);a[y].push_back(x);}dfs(1);int ans=0;for(int i=0;i<a[1].size();i++) {ans+=dp(a[1][i],2);}printf("%d",ans);return 0;
}