五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。
请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。
Input
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个通道端点的信息，依次为：该结点标号i（0
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
Output
最少的经费。
Sample Input
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
Sample Output
25
下面是我的代码，不知道为何WA 已经n++次了QAQ。。。就是找不出错误在哪里，。。第一次做树形dp，受打击呀。。。。希望各路前辈或者知道的人帮帮忙。到了这个地步感觉调试只能是浪费时间。。
#include
#include
#include
using namespace std;
const int MAXN = 1510;
int n;
int f[MAXN][2];
int vis[MAXN][MAXN];
int v0[MAXN];
int w[10010],a[10010],temp=0;
void dfs(int u){
v0[u] = true;
for(int i=1; i<=n;i++)
{
if(!vis[u][i])
{continue;}
if(v0[i])
{continue;}
dfs(i);
f[u][0]+=f[i][1];
f[u][1]+=min(f[i][1],f[i][0]);
}
}
int main(){
scanf("%d", &n);
int x,v,u;
memset(vis, 0, sizeof(vis));
memset(v0,0,sizeof(v));
for(int i=1; i<=n; i++){
scanf("%d%d%d", &a[i],&w[i],&x);
while(x--){
scanf("%d", &v);
vis[a[i]][v]=1;vis[v][a[i]]=1;
}
}
for(int i=0; i<=n; i++)
{f[i][1] = w[i]; f[i][0] = 0; }
if(n==1)
{printf("%d\n",w[n]);return 0;}
else dfs(1);
printf("%d\n", min(f[1][0], f[1][1]));
return 0;
}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/887/viewspace-3167182/ ，如需转载，请注明出处，否则将追究法律责任。
