P
r
o
b
l
e
m
\mathrm{Problem}
Problem
从前有棵树。
找出
K
K
K 个点
A
1
，
A
2
，
…
，
A
k
A_1，A_2，…，A_k
A1，A2，…，Ak。
使得
∑
d
i
s
(
A
i
,
A
i
+
1
)
,
(
1
≤
i
<
K
)
∑dis(Ai,Ai+1),(1\le i<K)
∑dis(Ai,Ai+1),(1≤i<K)最小。
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
题目可以转化为，从
a
1
a_1
a1出发需要依次遍历这些点，求行走路径步数的最小值。
显然，这
k
k
k 个点一定是一个连通块，否则一定能找到一个比答案更优的方案。如果我们选定了这连通块，我们会发现最短路径长度一定是
2
k
−
m
a
x
l
e
n
2k-\mathrm{maxlen}
2k−maxlen，
m
a
x
l
e
n
\mathrm{maxlen}
maxlen表示树的直径的长度。那么直径上的点被计算了两遍，而其他点则被计算了一遍。
现在我们树形DP，设
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k]表示以
i
i
i 为根的子树中，选择了
j
j
j 个点的方案，其中有
k
k
k 个直径端点在该连通块内。
当前子树
y
y
y 以及原来统计的子树都不存在直径端点时，这条边贡献为
2
v
2v
2v。当前子树
y
y
y 存在直径的一个端点，贡献为
v
v
v。当前子树
y
y
y 存在直径的两个端点，则这条边贡献为
2
v
2v
2v。当前子树
y
y
y 不存在直径端点时，贡献为
2
v
2v
2v。
然后就暴力转移即可。
C
o
d
e
\mathrm{Code}
Code
#include <bits/stdc++.h>
using namespace std
;
const int N
= 4000;
int n
, m
, res(1e9);
int f
[N
][N
][4], size
[N
];
vector
< pair
<int,int> > a
[N
];
int read(void)
{
int s
= 0, w
= 0; char c
= getchar();
while (c
< '0' || c
> '9') w
|= c
== '-', c
= getchar();
while (c
>= '0' && c
<= '9') s
= s
*10+c
-48, c
= getchar();
return w
? -s
: s
;
}
#define f(a,b,c) f[a][b][c]
#define upd(x,y) x = min(x,y);
void Dfs(int x
,int fa
)
{
size
[x
] = 1;
f
[x
][1][0] = f
[x
][1][1] = f
[x
][1][2] = 0;
for (int i
=0;i
<a
[x
].size();++i
)
{
int y
= a
[x
][i
].first
;
int v
= a
[x
][i
].second
;
if (y
== fa
) continue;
Dfs(y
,x
);
for (int j
=min(size
[x
],m
);j
>=0;--j
) {
for (int k
=min(size
[y
],m
);k
>=0;--k
) {
upd(f(x
,j
+k
,0),f(x
,j
,0)+f(y
,k
,0)+2*v
);
upd(f(x
,j
+k
,1),f(x
,j
,0)+f(y
,k
,1)+v
);
upd(f(x
,j
+k
,1),f(x
,j
,1)+f(y
,k
,0)+2*v
);
upd(f(x
,j
+k
,2),f(x
,j
,1)+f(y
,k
,1)+v
);
upd(f(x
,j
+k
,2),f(x
,j
,2)+f(y
,k
,0)+2*v
);
upd(f(x
,j
+k
,2),f(x
,j
,0)+f(y
,k
,2)+2*v
);
}
}
size
[x
] += size
[y
];
}
res
= min(res
,f
[x
][m
][2]);
return;
}
signed main(void)
{
n
= read(), m
= read();
memset(f
,30,sizeof f
);
for (int i
=1;i
<n
;++i
)
{
int x
= read(), y
= read(), v
= read();
a
[x
].push_back({y
,v
});
a
[y
].push_back({x
,v
});
}
Dfs(1,0);
cout
<< res
<< endl
;
return 0;
}
