树上动态规划模型
对于求一些树上的最优解问题，我们常常用 d[u][i] 来表示 u 结点 的一些值，而树上动态规划常常使用逆推，即由叶子结点向上推出 根节点的答案
d[u] = min/max( d[v] + w ) v是u的字结点
题目链接
题意：给出一个计算机网络，选取其中给一部分作为服务器，问最少选择几个服务器。
解题报告：
有三种状态：
dp[u][0] : 选择u结点
dp[u][1]: 选择u结点的字结点
dp[u][2]: 选择u结点的父亲结点
状态转移方程：
dp[u][0]=min(dp[v][0],dp[v][2])+1
dp[u][2]+=dp[v][1]
dp[u][1]=min(dp[u][2]-dp[v][1]+dp[v][0])
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 1e4 + 100;
int dp[N][4];
vector<int> G[N];void d(int u, int fa){int k=G[u].size();for ( int i=0; i<k; i++ ){int v=G[u][i];if( v==fa ) continue;d(v, u);dp[u][0]+=min(dp[v][0],dp[v][2]);dp[u][2]+=dp[v][1];dp[u][1]=min(dp[u][1],dp[v][0]-dp[v][1]);}dp[u][1]+=dp[u][2];
}int main(){int n;while( scanf("%d", &n )==1 && n!=-1 ){if( !n ) continue;for ( int i=1; i<=n+10; i++ ) G[i].clear();for ( int i=1; i<=n+10; i++ ) dp[i][0]=1, dp[i][2]=0, dp[i][1]=1e6;for ( int i=1; i<n; i++ ){int x, y;scanf("%d%d", &x, &y );G[x].push_back(y);G[y].push_back(x);}d(1,0);printf("%d\n", min(dp[1][1],dp[1][0]) );}
}