desprition
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。
编程任务：
请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。
solution
一开始自己拿战略游戏那道题的思路写了这道题，然后就获得了 (10pts) 的好成绩。
仔细想想这两道题之间还是有区别的：
- 战略游戏是每条边的左右端点至少选一个。
- 但这道题不太一样，这两个点可以都不选，比如左端点被他的父亲覆盖，然后右端点被他儿子覆盖。
这样我们的状态设计就出现了问题。
考虑到一个点只会被他自己，他儿子或者他父亲覆盖。
然后就设 (f[i][0/1/2]) 分别表示 在这个点放/在这个点的儿子处放/在这个点的父亲处放的最小花费。
初始化： (f[i][0] = a[i], f[i][1] = f[i][2] = 0)
特别的当 (i) 为叶子节点时， (f[i][1] = inf) ，因为他下面没有儿子可以覆盖。
转移
- (f[i][0] += min(f[to][0],f[to][1],f[to][2]))
加入在 (i) 这个点放的话，那么他的儿子可以任意放。
- (f[i][2] += min(f[to][0],f[to][1]))
这个时候因为 (i) 这个节点没有放，所以就不能由 (f[to][1]) 转移过来。
- (f[i][1] += min(f[to][0],f[to][1])) 至少选一个 (f[to][0])
这个时候只需要满足至少有一个儿子节点放就行，其他儿子随便放。
这个直接转移是 (O(n^2)) 的，考虑优化。
记录一个差值 (tmp = min(tmp,max(0,f[to][0]-f[to][1])))
如果 (tmp == 0) 说明我们至少选了 一个 (f[to][1]) ,而 (tmp) 不为零的时候直接把差值最小的那个即 (tmp) 加上去就行。
最后答案 (min(f[1][0],f[1][1])) 因为 (1) 没有父亲节点，所以自然也不存在被父亲覆盖这种情况。
又水了两道蓝题呢，(◕ᴗ◕✿)。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
const int inf = 2333333;
int n,x,son,tot;
int head[N],siz[N],a[N],f[N][3];
struct node
{
int to,net;
}e[N<<1];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
void dfs(int x,int fa)
{
f[x][0] = a[x];
f[x][1] = f[x][2] = 0;
int tmp = inf;
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(to == fa) continue;
dfs(to,x);
f[x][0] += min(f[to][0],min(f[to][1],f[to][2]));
f[x][1] += min(f[to][0],f[to][1]);
f[x][2] += min(f[to][0],f[to][1]);
tmp = min(tmp,max(0,f[to][0]-f[to][1]));
}
if(siz[x] == 0) f[x][1] = inf;
else f[x][1] += tmp;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++)
{
x = read(); a[x] = read(); siz[x] = read();
for(int i = 1; i <= siz[x]; i++)
{
son = read();
add(x,son); add(son,x);
}
}
dfs(1,1);
printf("%d
",min(f[1][0],f[1][1]));
return 0;
}