#223. 树上染色
-
ID: 223
传统题
1000ms
256MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
树上染色
说明
有一棵点数为 NNN 的树，树边有边权。给你一个在 0∼N0 \sim N0∼N 之内的正整数 KKK，你要在这棵树中选择 KKK 个点，将其染成黑色，并将其他的 N−KN-KN−K 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
输入格式
第一行两个整数 N,KN,KN,K。
接下来 N−1N-1N−1 行每行三个正整数 fr,to,dis\text{fr}, \text{to} , \text{dis}fr,to,dis，表示该树中存在一条长度为 dis\text{dis}dis 的边 (fr,to)(\text{fr},\text{to})(fr,to)。
输入保证所有点之间是联通的。
<div class="row">
<div class="column">
<h4 class="ui top attached block header">输出格式</h4>
<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>输出一个正整数，表示收益的最大值。</p>
<div class="row">
<div class="column">
<h4 class="ui top attached block header">样例</h4>
<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><h4>样例输入</h4>
5 2
1 2 3
1 5 1
2 3 1
2 4 2样例输出
17样例解释
将点 1,21,21,2 染黑就能获得最大收益。
</div></div> </div> </div><div class="row">
<div class="column">
<h4 class="ui top attached block header">数据范围与提示</h4>
<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p><span class="katex"><span class="katex-mathml">N≤2000, 0≤K≤NN \leq 2000, \ 0 \leq K \leq N</span><span class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.8777699999999999em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="mrel">≤</span><span class="mord mathrm">2</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mpunct">,</span><span class="mord mspace"> </span><span class="mord mathrm">0</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.07153em;">K</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.10903em;">N</span></span></span></span></p>
<div class="row">
<div class="column">