题目大意

图论中的树为一个无环的无向图。

给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。

开始的时候，所有的指示灯都是熄灭的。

请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

对于 \(100 \%\) 的数据，满足 \(1 \leq n \leq 100\)。

解题思路

先解释一下直接邻居，就是一个节点有边连向的节点，也就是父节点和子节点。

显然对于这种题，优先考虑贪心和树形 DP，贪心比较难想，那选择树形 DP 吧。

先看一道弱化题。

正解是树形 DP。

设 \(f[x][0]\) 表示以 \(x\) 为根的子树，且 \(x\) 不参加舞会的最大快乐值，

\(f[x][1]\)表示以 \(x\) 为根的子树，且 \(x\) 参加了舞会的最大快乐值。

则 \(f[x][0]=max(f[y][0],f[y][1])\)。（\(y\) 是 \(x\) 的儿子）

\(f[x][1]=f[y][0]+h[x]\)。（\(y\) 是 \(x\) 的儿子）

先找到唯一的树根 root，则 \(ans=max(f[root][0],f[root][1])\)。

对于这题，显然也有类似的思路。

记：

• \(dp_{u,0,0}\) 表示节点 \(u\) 不按按钮且不亮；

• \(dp_{u,0,1}\) 表示节点 \(u\) 不按按钮且亮；

• \(dp_{u,1,0}\) 表示节点 \(u\) 按按钮且按了之后不亮；

• \(dp_{u,1,1}\) 表示节点 \(u\) 按按钮且按了之后亮。

在树形 DP 时一定要满足整个子树都是亮的。

于是来一波转移方程的推导（\(v\) 是 \(u\) 的子节点）：

• \(dp_{u,0,0}=\min\{dp_{u,0,1}+dp_{v,1,1},dp_{u,0,0}+dp_{v,0,1}\}\)。

• \(dp_{u,0,1}=\min\{dp_{u,0,0}+dp_{v,1,1},dp_{u,0,1}+dp_{v,0,1}\}\)。

• \(dp_{u,1,0}=\min\{dp_{u,1,1}+dp_{v,1,0},dp_{u,1,0}+dp_{v,0,0}\}\)。

• \(dp_{u,1,1}=\min\{dp_{u,1,0}+dp_{v,1,0},dp_{u,1,1}+dp_{v,0,0}\}\)。

边界条件：

f[u][1][0] = f[u][0][1] = 0x3f;
f[u][1][1] = 1;
f[u][0][0] = 0;

AC CODE

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define _ 210

int n;

int tot, head[_], to[_ * 2], nxt[_ * 2];

int f[_][2][2];

void add(int u, int v)
{
	to[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
}

void dfs(int u, int fa)
{
	f[u][1][0] = f[u][0][1] = 0x3f;
	f[u][1][1] = 1;
	f[u][0][0] = 0;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);
		// 这里用的是前面未更新的值，需要先储存起来，最后再赋值。
		int t1 = min(f[u][0][1] + f[v][1][1], f[u][0][0] + f[v][0][1]);
		int t2 = min(f[u][0][0] + f[v][1][1], f[u][0][1] + f[v][0][1]);
		int t3 = min(f[u][1][1] + f[v][1][0], f[u][1][0] + f[v][0][0]);
		int t4 = min(f[u][1][0] + f[v][1][0], f[u][1][1] + f[v][0][0]);
		f[u][0][0] = t1;
		f[u][0][1] = t2;
		f[u][1][0] = t3;
		f[u][1][1] = t4;
	}
}

signed main()
{
	while(1)
	{
	 	scanf("%lld", &n);
		if(!n) break;
		tot = 0;
		memset(head, 0, sizeof head);
		memset(f, 0x3f, sizeof f);
		for(int i = 1; i < n; ++i)
		{
			int u, v;
			scanf("%lld%lld", &u, &v);
			add(u, v);
			add(v, u);
		}
		dfs(1, 0);
		printf("%lld\n", min(f[1][0][1], f[1][1][1]));
	}
}