首先这肯定是一个树形DP(因为用tag搜的
一开始用的是2种状态，放没放塔，但是其实还有一种没放塔但是被覆盖的。
然后就自己在草稿纸上画一画，把几个状态转移方式弄出来，0表示没放塔没被覆盖，1表示放了塔，2表示没放塔被覆盖了。
dp[x][0]+=dp[y][2]; 因为这个点不放就要保证他的儿子都是被覆盖了的，然后因为2状态肯定比1小，所以加2就行
dp[x][1]加上三个里面最小的之后再加1
dp[x][2]加上所有2之后再加上一个1-2的最小值，因为要保证儿子里面有一个放了
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int INF = 0X3f3f3f3f; 6 int tot = 0, Next[30005], to[30005], head[15005], dp[15005][3], n; 7 void add(int a, int b) { 8 Next[tot] = head[a], to[tot] = b; 9 head[a] = tot++; 10 } 11 void dfs(int x, int pre) { 12 for (int i = head[x]; i != -1; i = Next[i]) { 13 int y = to[i]; 14 if (y != pre) { 15 dfs(y, x); 16 } 17 } 18 int minn = INF; 19 for (int i = head[x]; i != -1; i = Next[i]) { 20 int y = to[i]; 21 if (y != pre) { 22 dp[x][1] += min(min(dp[y][1], dp[y][0]), dp[y][2]); 23 dp[x][0] += dp[y][2]; 24 dp[x][2] += min(dp[y][2], dp[y][1]); 25 minn = min(minn, dp[y][1] - dp[y][2]); 26 } 27 } 28 if (minn > 0 && minn != INF) { 29 dp[x][2] += minn; 30 } 31 dp[x][1]++; 32 if (dp[x][2] == 0) { 33 dp[x][2] = 1; 34 } 35 } 36 int main() { 37 scanf("%d", &n); 38 memset(dp, 0, sizeof(dp)); 39 for (int i = 1; i <= n; i++) 40 head[i] = -1; 41 for (int i = 1; i < n; i++) { 42 int x, y; 43 scanf("%d%d", &x, &y); 44 add(x, y); 45 add(y, x); 46 } 47 dfs(1, -1); 48 if (n == 1) { 49 printf("1 "); 50 return 0; 51 } 52 printf("%d ", min(dp[1][1], dp[1][2])); 53 return 0; 54 }