算是我的第一个树形DP 的题：
题目意思：N个城市形成树状结构。现在建立一些消防站在某些城市；每个城市有两个树形cost（在这个城市建立消防站的花费），limit ；
我们要是每个城镇都是安全的：就是每个距离这个城镇最近的消防站不能超过这个城镇的limit值；
解法：这个题目乍一看卧槽怎么玩！玩不了啊！先给出dp[i][j]( I 依靠J，并且 I 这课子树都已经被覆盖的最优解（不一定都被J覆盖）)；
假设一个节点的亲儿子树都被解决完毕,我们对于这些 亲儿子树 和这个 节点所组成的树的解如何得出？
初始化dp[i][j]=cost[j];
无疑使枚举这个节点I 依靠的节点，然后得出最小值;
而这些 亲子树的合并无疑有俩情况
1：这些亲儿子树依靠这个节点J 值 dp[k][j]-cost[j];
2：这些亲儿子树不依靠这个节点I 值
{
int best=0x7fffffff;
for（int w=1;w<=n;w++）
best=min(dp[k][w],best);
>>>best;
}
所以我们要开一个数字组维护每个节点的最值；
我输得不清楚那么百度下“国家集训队2006论文集 陈启峰”
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=;
const int INF=0x7fffffff;
struct Edge
{
int to,dis,pre;
Edge(int to=,int dis=,int pre=):to(to),dis(dis),pre(pre){}
};
Edge edge[maxn*];
int head[maxn],pos;
int dp[maxn][maxn];
int dis[maxn][maxn];
int limit[maxn],cost [maxn];
int best[maxn];
int n,start; void inint()
{
for(int i=;i<maxn;i++)
{
best[i]=INF;
for(int j=;j<maxn;j++)
dp[i][j]=INF;
}
memset(head,-,sizeof(head));
pos=;
}
void add_edge(int s,int to,int dis)
{
edge[pos]=Edge(to,dis,head[s]);
head[s]=pos++;
}
void DIS(int pa,int s)
{
for(int i=head[s];~i;i=edge[i].pre)
{
Edge &tmp=edge[i];
if(tmp.to==pa)continue;
dis[start][tmp.to]=dis[start][s]+tmp.dis;
DIS(s,tmp.to);
}
}
void dfs(int pa,int s)
{
for(int i=head[s];~i;i=edge[i].pre)
{
Edge &tmp=edge[i];
if(tmp.to==pa)continue;
dfs(s,tmp.to);
}
for(int i=;i<=n;i++)
if(dis[s][i]<=limit[s])
{
dp[s][i]=cost[i];
for(int j=head[s];~j;j=edge[j].pre)
{
Edge &tmp=edge[j];
if(tmp.to==pa)continue;
dp[s][i]+=min(dp[tmp.to][i]-cost[i],best[tmp.to]);//加等
}
best[s]=min(best[s],dp[s][i]);
}
}
int main()
{
int t;
int a,b,c;
scanf("%d",&t);
while(t--)
{
inint();
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&cost[i]);
for(int i=;i<=n;i++)scanf("%d",&limit[i]); for(int i=;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
for(int i=;i<=n;i++)start=i,DIS(-,i);
dfs(-,);
printf("%d\n",best[]);
}
return ;
}