城市规划

第一次独立做出第五题，感觉这道题目比起别的第五题来说不算太难，一看是一棵树可以直接想到树形dp，这道题目就是一个树形dp，设dp i,j为第i个点下选了j个点的最大值，另外就是如果这个点是重要的点就令dp i,1=0 转移考虑树形背包的转移方式，通过画图可以知道dp to(子节点),x 连接 dp i,j的边要走 x(k-x)次，直接转移就行了，虽然表面上复杂度为nk*k过不了，但就是过了。。

ACwing上面数据太强了，导致我有时候能A有时候TLE，但是CCF数据有点水我只用了300ms就过了
CCF: http://118.190.20.162/view.page?gpid=T90

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const int N = 5e4+7;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> tr;
ll gcd(ll a, ll b){ return a == 0 ? b : gcd(b % a, a); }
ll exgcd(ll a,ll b,ll&x,ll&y){if(b==0){x=1,y=0;return a;}else{ll r=exgcd(b,a%b,x,y),t=x;x=y;y=t-a/b*x;return r;}}//注意x,y一定为ll

int a[N],head[N],cnt=1,vis[N];
ll dp[N][107], inf = 1e15;
struct edge{
    int f,t,n;
    ll w;
}g[N*2];
int n,m,k,x;
void add(int f,int t,ll w){
    g[cnt].n = head[f];
    g[cnt].t = t;
    g[cnt].w = w;
    head[f] = cnt++;
}
void dfs(int u,int fa){
    dp[u][0] = 0;
    if(vis[u]) dp[u][1] = 0;
    for(int i=head[u];i;i=g[i].n){
        int to = g[i].t;
        if(to==fa) continue;
        dfs(to,u);
        for(int j=k;j>=1;j--){
            for(int w=j;w>=0;w--){
                dp[u][j] = min(dp[u][j],dp[u][j-w]+dp[to][w]+g[i].w*w*(k-w));
            }
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            dp[i][j] = inf;
    for(int i=1;i<=m;i++) cin>>x, vis[x]=1;
    for(int i=0;i<n-1;i++){
        int f,t,w;
        cin>>f>>t>>w;
        add(f,t,w), add(t,f,w);
    }
    dfs(1,0);
    cout<<dp[1][k];
}