POJ 2152

진계봉의 논문 문제
이 나무 모양 dp는 여전히 비교적 어려워서 생각지도 못했다.
pp[i][j]는 i를 뿌리로 하는 자수를 표시하고 i결점은 j를 담당역으로 선택하여 가장 적은 대가를 지불한다.
st[i]=min{dp[i][j]|1<=j<=n} dis[i][j]>limit[i], dp[i][j]=∞ dis[i][j]<=limit[i], dp[i][j]=cost[j]+sigma {min(best[child[i]]]], dp[child[i]]]][j]-cost[j])]

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
#define inf 0x3f3f3f3f
using namespace std;

int n,cost[N],limit[N],tim[N],dep,son[N];
int dis[N][N];
int dp[N][N],best[N];
int head[N],cnt;
struct Edge{
	int v,w,next;
}edge[N*2];

void init(){
	memset(head,-1,sizeof(head));
	memset(tim,0,sizeof(tim));
	cnt=dep=0;
}

void addedge(int u,int v,int w){
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
	edge[cnt].v=u;
	edge[cnt].w=w;
	edge[cnt].next=head[v];
	head[v]=cnt++;
}

void init_dfs(int u,int fa){
	tim[u]=++dep;
	son[u]=1;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa)continue;
		init_dfs(v,u);
		son[u]+=son[v];
	}
}

void cal_dis(int u,int fa,int now){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa)continue;
		dis[now][v]=dis[now][u]+edge[i].w;
		cal_dis(v,u,now);
	}
}

void dfs(int u,int fa){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa) continue;
		dfs(v,u);
	}
	best[u]=inf;
	for(int j=0;j<n;j++){
		if(dis[u][j]<=limit[u]){
			dp[u][j]=cost[j];
			for(int i=head[u];i!=-1;i=edge[i].next){
				int v=edge[i].v;
				if(v==fa) continue;
				dp[u][j]+=min(best[v],dp[v][j]-cost[j]);  // u  j ，v    j           (   j   ，    ,          cost)，
				// v                        ，   min       
			}
			if(tim[j]>=tim[u] && tim[j]<=tim[u]+son[u]-1)
				best[u]=min(best[u],dp[u][j]);
		}
		else dp[u][j]=inf;
	}
}

int main(){
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;t++){
		init();
		scanf("%d",&n);
		for(int i=0;i<n;i++) scanf("%d",&cost[i]);
		for(int i=0;i<n;i++) scanf("%d",&limit[i]);
		for(int i=0;i<n-1;i++){
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			u--;v--;
			addedge(u,v,w);
		}
		init_dfs(0,-1);
		for(int i=0;i<n;i++){
			dis[i][i]=0;
			cal_dis(i,-1,i);
		}
		dfs(0,-1);
		printf("%d
",best[0]);
	}
}