紫书上的树形DP，挺香的。

\(\operatorname{Description}\)

给定一个 \(n\) 台计算机形成的树状结构。要求在其中一些计算机上安装服务器，使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最小数量。

\(\operatorname{Solution}\)

考虑维护一个树状结构，设 \(1\) 号点为根节点，双向建边。

考虑树形DP，设 \(f_u\) 为以 \(u\) 为根的子树。

• \(f_{u,1}\)：\(u\) 是服务器，则每个子节点可以是服务器也可以不是。

• \(f_{u,2}\)：\(u\) 不是服务器，但 \(u\) 的父亲是服务器，这意味着 \(u\) 的所有子节点都不是服务器。

• \(f_{u,3}\)：\(u\) 和 \(u\) 的父亲都不是服务器，这意味着 \(u\) 恰好有一个儿子是服务器。

然后我们考虑如何转移。

为了方便阐述，令 \(v\) 为 \(u\) 的子节点，定义集合 \(S\) 为 \(u\) 的所有子节点的集合。

首先可以写出：

\[f_{u,0}=\sum_{v∈S}\min(f_{v,0},f_{v,1})+1 \]

\[f_{u,1}=\sum_{v∈S}f_{v,2} \]

而 \(f_{v,2}\) 的转移稍微复杂一点，考虑遍历 \(v\)，则当前 \(v\) 为 \(u\) 子节点的唯一服务器，设其他所有子节点为 \(v'\)。得到：

\[f_{u,2}=\min(\sum_{v∈S}(f_{v,0}+\sum_{v'∈S-v}f_{v',2})) \]

由于 \(f_{u,2}\) 的转移是 \(O(n^2)\) 的，故考虑优化。

看到上文中的 \(f_{u,1}=\sum_{v∈S}f_{v,2}\)，所以对柿子进行处理后：

\[f_{u,2}=\min(\sum_{v∈S}(f_{v,0}+f_{u,1}-f_{v,2})) \]

考虑最后的答案，由于根结点并没有父亲节点，故为 \(\min(f_{1,0},f_{1,2})\)。

\(\operatorname{Code}\)

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int Inf=10005;
int n,f[N][3];
vector <int> q[N];
void dfs(int u, int fa) {
	f[u][0]=1; f[u][1]=0; f[u][2]=Inf;
	for(int i=0;i<q[u].size();i++) {
		if(q[u][i]==fa) continue;
		int v=q[u][i]; dfs(v,u);
		f[u][0] += min (f[v][1],f[v][0]);
		f[u][1] += f[v][2];
		f[u][2] = min (f[u][2],f[u][1]-f[v][2]+f[v][0]);
	}
}
void Clear() {for(int i=1;i<=n;i++) q[i].clear();}
int main() {
    while (cin >> n) {
    	Clear();
    	for(int i=1;i<n;i++) {
    		int x,y; cin >> x >> y;
    		q[x].push_back(y); q[y].push_back(x);
		}
		dfs(1,0);
    	printf("%d\n",min (f[1][0],f[1][2]));
    	int d; cin >> d; if(d==-1) break;
	}
	return 0;
}

本题解参考《算法竞赛入门经典》