Gym 101655 D Delta Quadrant —

Gym 101655 D Delta Quadrant —— 树形DP

本文主要是介绍Gym 101655 D Delta Quadrant —— 树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一棵树，每条边都有权值，你必须从一个点开始，包括这个点走上n-k个不同的点再回到这个点，问你走的路径权值和最小是多少。

题解：

比赛的时候被C卡住了，写了200行，，结果想法错了，当场爆炸，赛后发现这道水题。啧
首先画个图就知道就是取n-k个树上连续的点集，然后它们之间的边权*2.
dp[i][j]表示第i个点的子树不取j个的最小值是多少。
那么转移就需要一些技巧，首先对于第一个儿子的转移直接赋值，其它儿子的话，就枚举当前点+新儿子放弃的个数的同时枚举当前点放弃的个数，注意有整个儿子子树都不取的情况，此时边权不需要加。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+5;
const ll inf=1e18;
struct node{int to,next;ll v;
}e[N*2];
int cnt,head[N],n,k;
void add(int x,int y,ll v){e[cnt].to=y;e[cnt].next=head[x];e[cnt].v=v;head[x]=cnt++;
}
ll dp[N][25],siz[N],sum[N],ans;
void dfs(int x,int fa){siz[x]=1;int f=0;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa)continue;ll v=e[i].v;dfs(ne,x);siz[x]+=siz[ne];if(!f){for(int j=0;j<=k;j++)dp[x][j]=v+dp[ne][j];if(siz[ne]<=k)dp[x][siz[ne]]=0;}else{ll ret[25];for(int j=0;j<=k;j++)ret[j]=inf;for(int j=0;j<=k;j++){for(int l=0;l<=j;l++){if(siz[ne]<=j-l)ret[j]=min(ret[j],dp[x][l]);elseret[j]=min(dp[x][l]+dp[ne][j-l]+v,ret[j]);}}for(int j=0;j<=k;j++)dp[x][j]=ret[j];}f=1;}for(int i=0;i<=k;i++)if(dp[x][i]>=inf)dp[x][i]=0;if(n-siz[x]<=k)ans=min(ans,dp[x][k-(n-siz[x])]);
}
int main()
{int T; scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);memset(head,-1,sizeof(head));cnt=0;ans=inf;int x,y;ll v;for(int i=1;i<n;i++){scanf("%d%d%lld",&x,&y,&v);add(x,y,v),add(y,x,v);}for(int i=0;i<n;i++)for(int j=0;j<=k;j++)dp[i][j]=inf;dfs(0,-1);printf("%lld\n",ans*2);}return 0;
}