题意
给你一个图，需要给每个点分配一个信息中心，在点上建立信息中心需要花费 $k$；此外，传输代价为d[点到其中心的距离]。求最小总代价及分配方案。
题解
开始发现dp状态不是很好设计，所以可以考虑dp的性质——无后效性，即无需考虑当前会对未来造成什么影响。
而当前状态是由之前的状态（叶节点的状态转移而来），所以可以设 $f_{u,i}$ 表示 $u$ 子树被分配到 $i$ 的代价。
转移的时候就讨论一下叶节点是否也分配到了 $i$ 即可。
初始状态？
在叶节点时 $f_{u,i}=k+d[dis_{u,i}]$
向上推，如果和某一个儿子使用一样的中心，那么就减去重复的k即可；如果不用一样的中心，那么就选儿子最小代价的方案转移过来。
所以 $f_{u,i}=k+d[dis_{u,i}]+\sum_{(u,v)}min(f_{v,i}-k,f_{v,mn[v]})$ （其中 $mn[v]$ 代表 $f_{v,i}$ 中最小的那个 $i$）
那么就做好啦，输出方案只需要从根开始往下搜，每次是从哪种情况转移来的即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int d[200];
int dis[200][200];
struct edge{
int to,nxt;
}ed[400];int edcnt=0;
int hd[200];
inline void adde(int u,int v){
ed[++edcnt]={v,hd[u]};
hd[u]=edcnt;
}
int dp[200][200],cho[200][200],mn[200];
void dfs(int u,int fa){
for(int i=1;i<=n;++i)dp[u][i]=k+d[dis[u][i]];
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa)continue;
dfs(v,u);
for(int i=1;i<=n;++i){
dp[u][i]+=min(dp[v][i]-k,dp[v][mn[v]]);
}
}
for(int i=1;i<=n;++i){
if(!mn[u]||dp[u][mn[u]]>dp[u][i])mn[u]=i;
}
}
int ans[200];
void dfs2(int u,int i,int fa){
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa)continue;
if(dp[v][i]-k<dp[v][mn[v]]){
ans[v]=i;
dfs2(v,i,u);
}else{
ans[v]=mn[v];
dfs2(v,mn[v],u);
}
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;++i)scanf("%d",&d[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)dis[i][j]=(i==j?0:10000);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
adde(u,v);adde(v,u);
dis[u][v]=dis[v][u]=1;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
dfs(1,1);
cout<<dp[1][mn[1]]<<endl;
dfs2(1,mn[1],1);
ans[1]=mn[1];
for(int i=1;i<=n;++i)printf("%d ",ans[i]);
}