Steven_MengのBlog

传送门

先上一个结论,所有$k$个节点应该构成一棵树,形状是原树的直径连着一堆子树,其中直径只经过一遍,子树的所有边经过两次,走法就是从直径的一段走到另一端,但是中途会离开直径,到某个和当前节点相连的子树逛一圈再回到这个节点。

所以子状态就有了,$dp[u][j][0/1/2]$表示$u$的子树里面选$j$个点,而且$u$的子树里面有多少直径的端点。

分六种情况考虑。


$dp[u][j+k][0]$只能从$dp[u][j][0]$,$dp[v][k][0]$转移而来,显然边$$不属于直径,所以要算两遍:

1
chkmin(dp[u][j+k][0],dp[u][j][0]+dp[v][k][0]+len*2);

$dp[u][j+k][1]$:转移有两种情况:

$a.dp[u][j][1],dp[v][k][0]$转移而来,如图所示,直径一定穿过$u$,所以$$算两次。

1
chkmin(dp[u][j+k][1],dp[u][j][1]+dp[v][k][0]+len*2);

$b.dp[u][j][0],dp[v][k][1]$转移而来,如图所示,直径穿过$$,$$只算一次。

1
chkmin(dp[u][j+k][1],dp[u][j][0]+dp[v][k][1]+len);

$dp[u][j+k][2]$:转移有三种情况:

$a.dp[u][j][0],dp[v][k][2]/dp[u][j][2],dp[v][k][0]$,转移而来,发现直径只可能整个缩在$u/v$的子树之中,所以算两次。

1
2
chkmin(dp[u][j+k][2],dp[u][j][0]+dp[v][k][2]+len*2);
chkmin(dp[u][j+k][2],dp[u][j][2]+dp[v][k][0]+len*2);

$b.dp[u][j][1],dp[v][k][1]$转移而来,发现直径经过$$,所以算一次

1
chkmin(dp[u][j+k][2],dp[u][j][1]+dp[v][k][1]+len);

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define MAXN 3005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,m;
struct Edge{
int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
G[u].push_back(Edge{v,w});
}
int dp[MAXN][MAXN][4],sz[MAXN];
inline void chkmin(int &a,int b){
if (a>b) a=b;
}
void dfs(int u,int father){
sz[u]=1;
dp[u][1][0]=dp[u][1][1]=dp[u][1][2]=0;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i].to,len=G[u][i].len;
if (v==father) continue;
dfs(v,u);
for (register int j=min(m,sz[u]);j>=1;--j){
for (register int k=1;k<=min(m,sz[v]);++k){
if (j+k>m) continue;
chkmin(dp[u][j+k][0],dp[u][j][0]+dp[v][k][0]+len*2);
chkmin(dp[u][j+k][1],dp[u][j][1]+dp[v][k][0]+len*2);
chkmin(dp[u][j+k][1],dp[u][j][0]+dp[v][k][1]+len);
chkmin(dp[u][j+k][2],dp[u][j][1]+dp[v][k][1]+len);
chkmin(dp[u][j+k][2],dp[u][j][0]+dp[v][k][2]+len*2);
chkmin(dp[u][j+k][2],dp[u][j][2]+dp[v][k][0]+len*2);
}
}
sz[u]+=sz[v];
}
}
int main(){
n=read(),m=read();
for (register int i=1;i<n;++i){
int u=read(),v=read(),w=read();
AddEdge(u,v,w);
AddEdge(v,u,w);
}
memset(dp,0x3f,sizeof(dp));
dfs(1,1);
int ans=0x7fffffff;
for (register int i=1;i<=n;++i) ans=min(ans,dp[i][m][2]);
printf("%d\n",ans);
}

 评论