CCF城市规划

暴力没法拿满分，也想不到有什么图论算法或树算法是可以解决这个题的，大概这时候就可以想想怎么dp了，又是树型结构，那应该考虑树形dp了。要算两两之间的距离的和，这种看上去好像是只能n方解决的，应该要注意到可能是分解成每一个部分算贡献(不然咋做呢)。考虑怎么划分集合定义dp，对于树形dp首先第一维应该是节点，第二维考虑题目的子问题，即选了多少个重要节点。dp[i][j]：在i节点下选了j个重要节点对于最终答案(最后的总和)的贡献。在分析转移，对于每个节点i都是由他的子树转移而来，在每个子树v都有min(sum[v],j)个决策(即在每个子树里都可以分别选择1到min(sum[v],j)个重要节点，并且每个选择都是互斥的)（sum[v]是在子树v里的重要点的数量）。这样就像是分组背包，每个子树是一个分组，在每个分组中选择一个决策。

#include <bits/stdc++.h>

using namespace std;
#define maxn 50010
#define inf 1e15
#define ll long long 
vector<pair<int,ll> > g[maxn];
ll dp[maxn][400];
int sum[maxn];
int vis[maxn];
int n,m,k;
void dfs(int now,int fa)
{
    for(int i=0;i<=k;i++) dp[now][i]=inf;
    dp[now][0]=0;
    if(vis[now]) sum[now]=1,dp[now][1]=0;
    for(auto x: g[now]){    //分组背包，枚举分组
        if(x.first==fa) continue;
        dfs(x.first,now);
        sum[now]+=sum[x.first];
        for(int i=min(k,sum[now]);i;i--){     //枚举体积
            for(int j=0;j<=min(i,sum[x.first]);j++){    //枚举决策
                dp[now][i]=min(dp[now][i],dp[x.first][j]+dp[now][i-j]+1ll*(k-j)*j*x.second);//添加每条从now到个子节点的边对于答案的贡献
            }
        }
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);vis[x]=1;
    }
    for(int i=1;i<=n-1;i++){
        int u,v;ll w;
        scanf("%d %d %lld",&u,&v,&w);
        g[u].push_back(make_pair(v,w));
        g[v].push_back(make_pair(u,w));
    }
    dfs(1,-1);
    printf("%lld\n",dp[1][k]);
    return 0;
}