HDU-6820 / 2020杭电多校(五) 1007 Tree
题意：
在一个无根树上选择一个的子图，要求子图全联通且度数大于k 的点最多只有1个。问该子图最大的权值。
题解：
-
首先想到枚举这个子图中度数大于k的点，然扩展一下。这个方法复杂度太高。
-
可以发现叶子节点很好处理，可以从下往上处理，想到树形DP。(dp[u] [0]) 表示以u为根的子图无大于k的点的最大权值。(dp[u] [1]) 表示以u为根的子图有一个大于k的点的最大权值。我们首先默认 u 必定和其父节点 pre 连边。那么在 u 在子节点中最多连 (k - 1) 个节点。(这样做的原因是为了能够向上dp，如果u已经连了k个子节点，处理pre时无法确定与哪些子节点能连边)。 由于是最大权重，所以为了处理方便我们可以先对子节点按照(dp[v][0] + w) 从大到小排序。
-
(dp[u][0]:)
-
$dp[u][1]: $ 更新(dp[u][1]) 情况较多，需要仔细思考。先设u为根的子图中度数大于k的点为p。
-
情况1：(p=u) , 这时u是度大于k的点，那么为了权值更大肯定尽量多的连边。
[dp[u][1]=sum_{i = 1}^{sn}(dp[v][0]+w) ] -
情况2：(p=v_{0}) , 即度数大于k的点是u的一个子节点。这时u在子节点中连1个(dp[v][1])， (k-2)个(dp[v] [0])。为了使权值最大选(dp[v][0]) 时一定从最大的点开始选择。由于子节点排好序，所以我们只需要讨论一下(v_{0})是不是前(k-1)个节点。设(sum=sum_{i=1}^{k-1}(dp[v_{i}][0]+w))
-
1）(v_{0})是前k-1个节点，那么就需要多选择一个第k-1个节点。(其中可以用(dp[u][0])代替sum)
[dp[u][1]=max{sum - (dp[v][0]+w) + (dp[v][1]+w)}\ dp[u][1]=max{dp[u][0]-dp[v][0]+dp[v][1]} ] -
2）(v_{0})不是前k-1个点，那么就只需要减去第k-1个点的值，加上(v_{0}) 的值就可以。其中mink1是第k-1个子节点的 (dp[v][0])+ w。
[dp[u][1]=max{dp[u][0]-mink1+dp[v][1]+w} \ ]
-
三种情况计算的(dp[u][1])取最大值。
-
-
前面部分dp时默认u与pre连边，现在我们要计算不u与pre不连边时的最大值。设(maxx1) 和 (maxx2) 分别表示此时的 (dp[u][0]) 和 (dp[u][1]) 。
-
若子节点个数大于等于k，(maxx1=dp[u][0]+mink) 。 否则 (maxx1=dp[u][0])
-
更新maxx2 ： 和计算(dp[u][1]) 的过程一样。不过(dp[u][1]) 是讨论(v_{0}) 是前K-1个点。(maxx2) 讨论 (v_{0}) 是前k个点。
[v属于{1...k}) maxx2 = max{maxx1-dp[v][0]+dp[v][1]} \ 其他 maxx2=max(maxx1-mink+dp[v][1]+w) ]
-
-
最后答案res = max(maxx1, maxx2)
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
const int N = 2e6 + 105;
const int mod = 998244353;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//
int n, k;
int head[N], cnt = 0;
ll dp[N][2];
ll res;
struct node{
int to, nxt; ll c;
}edge[N];
void add(int u, int v, ll w){
edge[cnt].to = v, edge[cnt].c = w, edge[cnt].nxt = head[u], head[u] = cnt ++;
edge[cnt].to = u, edge[cnt].c = w, edge[cnt].nxt = head[v], head[v] = cnt ++;
}
bool cmp(int a, int b){
return dp[edge[a].to][0] + edge[a].c > dp[edge[b].to][0] + edge[b].c;
}
void dfs(int u, int pre){
dp[u][0] = dp[u][1] = 0;
vector<int> sol; sol.push_back(0);
int sn = 0; //sonnum;
for(int i = head[u]; i != -1; i = edge[i].nxt){
int v = edge[i].to; ll w = edge[i].c;
if(v == pre) continue;
dfs(v, u);
sol.push_back(i);
sn ++;
}
sort(sol.begin() + 1, sol.begin() + 1 + sn, cmp);
ll maxx1 = 0, maxx2 = 0;
//dp[u][0] and maxx1
for(int i = 1; i <= min(k - 1, sn); ++ i){
int v = edge[sol[i]].to; ll w = edge[sol[i]].c;
dp[u][0] += dp[v][0] + w;
}
if(sn >= k) maxx1 = dp[u][0] + dp[edge[sol[k]].to][0] + edge[sol[k]].c;
else maxx1 = dp[u][0];
res = max(res, maxx1);
// dp[u][1] and maxx2
for(int i = 1; i <= sn; ++ i){
int v = edge[sol[i]].to; ll w = edge[sol[i]].c;
dp[u][1] += dp[v][0] + w;
}
maxx2 = dp[u][1];
for(int i = 1; i <= sn; ++ i){
int v = edge[sol[i]].to; ll w = edge[sol[i]].c;
if(i <= k - 1) dp[u][1] = max(dp[u][1], dp[u][0] - dp[v][0] + dp[v][1]);
else if(k > 1){
ll mink1 = dp[edge[sol[k - 1]].to][0] + edge[sol[k - 1]].c;
dp[u][1] = max(dp[u][1], dp[u][0] - mink1 + dp[v][1] + w);
}
}
for(int i = 1; i <= sn; ++ i){
int v = edge[sol[i]].to; ll w = edge[sol[i]].c;
if(i <= k) maxx2 = max(maxx2, maxx1 - dp[v][0] + dp[v][1]);
else if(k > 0){
ll mink = dp[edge[sol[k]].to][0] + edge[sol[k]].c;
maxx2 = max(maxx2, maxx1 - mink + dp[v][1] + w);
}
}
res = max(res, maxx2);
}
void init(){
cnt = 0;
res = 0;
for(int i = 0; i <= n + 2; ++ i){
head[i] = -1;
dp[i][0] = dp[i][1] = 0;
}
}
int main()
{
int T; scanf("%d",&T);
while(T --){
scanf("%d%d",&n,&k);
init();
for(int i = 1; i < n; ++ i){
int x, y; ll z; scanf("%d%d%lld",&x,&y,&z);
add(x, y, z);
}
if(!k){
printf("0
");
continue;
}
dfs(1, 0);
printf("%lld
", res);
}
return 0;
}