[中山市选2009]树

题目大意

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

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

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

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

对于 \(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]));
	}
}
上一篇:TCP/IP协议栈在Linux内核中的运行时序分析


下一篇:AI框架类FAQ