题意：给定一个树形的机器结构，安装服务器，每台服务器恰好跟一台服务器相邻，问最少装几台服务器。
首先DFS把树建立起来，然后动规求解，注意设置无穷大inf后累加要防止超int范围。
#define _CRT_SECURE_NO_WARNINGS#include#include #include #include #include #include #include using namespace std;const int maxn = 10240, inf = (1<<27);int n, vis[maxn], dp[maxn][3];vector G[maxn], sons[maxn];void DFS(const int u){ for (unsigned i = 0; i != G[u].size(); ++i) if(!vis[G[u][i]]) { sons[u].push_back(G[u][i]); vis[G[u][i]] = true; DFS(G[u][i]); }}int solve(const int u, const int k){ if (dp[u][k] != -1) return dp[u][k]; int & ans = dp[u][k]; if (k == 0) ans = 1; if (k == 1) ans = 0; if (k == 2) ans = inf; for (unsigned i = 0; i != sons[u].size(); ++i){ int v = sons[u][i]; if (k == 0) ans += min(solve(v, 0), solve(v, 1)); if (k == 1) ans += solve(v, 2); if (k == 2) ans = min(ans, solve(u, 1) - solve(v, 2) + solve(v, 0)); if (ans > inf) ans = inf; } return ans;}int main(){ //freopen("in.txt", "r", stdin); while (cin >> n){ memset(G, 0, sizeof(G)); memset(sons, 0, sizeof(sons)); memset(vis, 0, sizeof(vis)); memset(dp, -1, sizeof(dp)); for (int i = 1; i < n; ++i){ int x, y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } vis[1] = true; DFS(1); cout << min(solve(1, 0), solve(1, 2)) << endl; cin >> n; if (n == -1) return 0; } return 0;}