bzoj4987: Tree（树形dp）

Description

从前有棵树。

找出K个点A1，A2，…，Ak。

使得∑dis(AiAi+1),(1<=i<=K-1)最小。

Input

第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。

接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。

I<=k<=n。

l<x,y<=n

1<=z<=10^5

n <= 3000

Output

一行一个整数，表示最小的距离和。

Sample Input

10 7
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238

Sample Output

184524

首先，为了保证最优，选出的点相邻，而且对于每条边，如果要算上从$a_k$走到$a_1$的话，相当于每条边走了两遍

那么现在不用算$a_k$走到$a_1$，相当于是从这一个联通块里选出一条链去掉它的贡献，其余的边都要被计算两边，那么我们可以转化为选出一些边

考虑树形dp，设$f[i][j][k]$表示在第$i$个点及其子树中选出了$j$条边，$k$表示选边的状态，此时的最小代价

$k=0$表示从当前的根节点遍历一遍子树中选的边再回来，$k=1$，表示遍历完子树就不回来，$k=2$表示从子树中某一个点遍历到根节点再出去又回来到另一个端点

然后不难发现每一个数字代表的状态都能由数值加起来等于它的状态转移而来。比方说状态2，可以看做是由两个状态为1的状态拼起来得到

又发现当前根和子树之间的连边只有在$k=1$时算一遍，其他时候都算两遍

然后树形dp即可

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 7 char buf[1<<21],*p1=buf,*p2=buf;
 8 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
 9 int read(){
10     #define num ch-'0'
11     char ch;bool flag=0;int res;
12     while(!isdigit(ch=getc()))
13     (ch=='-')&&(flag=true);
14     for(res=num;isdigit(ch=getc());res=res*10+num);
15     (flag)&&(res=-res);
16     #undef num
17     return res;
18 }
19 const int N=3005;
20 int head[N],Next[N<<1],ver[N<<1],edge[N<<1],tot;
21 inline void add(int u,int v,int e){
22     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
23 }
24 int sz[N],f[N][N][3],n,m,ans=1<<30;
25 void dfs(int u,int fa){
26     sz[u]=1,f[u][0][0]=f[u][0][1]=0;
27     for(int i=head[u];i;i=Next[i]){
28         int v=ver[i];
29         if(v!=fa){
30             dfs(v,u);
31             for(int j=sz[u]-1;~j;--j)
32             for(int k=sz[v]-1;~k;--k)
33             for(int l=2;~l;--l)
34             for(int m=l;~m;--m)
35             cmin(f[u][j+k+1][l],f[u][j][l-m]+f[v][k][m]+edge[i]*(2-(m==1)));
36             sz[u]+=sz[v];
37         }
38     }
39 }
40 int main(){
41 //    freopen("testdata.in","r",stdin);
42     n=read(),m=read();
43     for(int i=1,u,v,e;i<n;++i)
44     u=read(),v=read(),e=read(),add(u,v,e),add(v,u,e);
45     memset(f,0x3f,sizeof(f));dfs(1,0);
46     for(int i=1;i<=n;++i) for(int j=0;j<=2;++j) cmin(ans,f[i][m-1][j]);
47     printf("%d
",ans);
48     return 0;
49 }