@@ 【noip赛前20天冲刺集训 day4】正在打模拟赛 @@
题目描述
给定一棵包含 n 个点的树，每条边都有权值，同时给定一个整数 k。定义一个树上连通块的权值为其中边权之和。你需要求解满足以下条件的树上连通块的权值最大值：这个连通块至多包含一个度数大于 k 的点。
注意，这里的度数指的是连通块内节点的度数，而不是原始树上的度数。
输入格式
第一行包含两个非负整数 n 和 k。
接下来 n - 1 行，每行包含三个非负正整数 u, v, w，表示一条边，其中 u 和 v 是连接的两个节点，w 是边的权值。
输出格式
输出一个非负整数，表示满足条件的连通块的最大权值。
样例
输入样例 1
8 2
1 4 1
2 4 2
3 4 4
4 5 8
5 6 16
5 7 32
5 8 64
输出样例 1
124
样例解释
在这个样例中，可以选择由节点 3, 4, 5, 6, 7, 8 组成的连通块。
数据范围
本题包含多个子任务，其数据范围如下：
子任务 1：n ≤ 2 × 10^3，无特殊性质，分值 18。
子任务 2：n ≤ 2 × 10^5，k ≤ min{10, n - 1}，分值 21。
子任务 3：n ≤ 2 × 10^5，对于 ∀i∈[2,n]，存在边 (i-1, i)，分值 13。
子任务 4：n ≤ 2 × 10^5，对于 ∀i∈[2,n]，存在边 (1, i)，分值 12。
子任务 5：n ≤ 2 × 10^5，无特殊性质，分值 36。
对于所有数据，保证 1 ≤ n ≤ 2 × 10^5，0 ≤ k < n，0 ≤ w ≤ 10^9。
解题思路
这个问题要求我们在一个树形结构中找到一个特定的连通块，其中至多只有一个节点的度数可以超过k，而且我们需要最大化这个连通块中所有边的权重和。这是一个优化问题，涉及到在满足特定条件的情况下最大化一个参数（本例中是边的权重和）。为了解决这个问题，我们将使用换根动态规划结合贪心策略。
换根动态规划
-
首先，我们对树进行一次深度优先搜索（DFS），这个搜索帮助我们计算两件事：
-
对于每个节点 u，我们都找出了一个包含 u 的连通块，这个连通块中的每个节点的度数都不超过 k，同时 u 的度数小于 k，同时我们尽可能地最大化了这个连通块中边的权重和。这是通过
dfs0函数完成的。 -
接下来，我们需要考虑的是：如果我们移除了 u 及其子树，我们能否在包含 u 的父节点的子树中找到一个新的连通块，同时满足度数限制并且也尽可能地最大化边的权重和。这就是为什么我们需要进行第二次DFS，并且在这次DFS中，我们会“换根”。这是通过
dfs1函数完成的。
贪心策略
-
在我们的DFS过程中，我们实际上在每个步骤中都在应用贪心策略。我们的目标是最大化连通块的边权和，因此我们总是倾向于选择权重最大的边。在
dfs0中，我们将每个节点的所有子树的权值存储在一个数组中，并对其进行排序，这样就可以很容易地选择权值最大的边。 -
在
dfs1中，我们对父节点应用了类似的策略，但这次是在考虑了“换根”之后。我们试图构建一个新的连通块，它包含了当前节点的父节点，并且在满足度数限制的同时，也尽可能地最大化了边的权重和。 -
通过这种方式，换根动态规划允许我们考虑树中的所有可能的连通块，而贪心策略则确保我们在满足度数限制的同时最大化了边的权重和。结合这两种策略，我们能够有效地遍历整棵树，找到满足题目要求的权值最大的树上连通块。
#include <bits/stdc++.h>
using namespace std;
#define int long long // 使用宏定义将int定义为长整型，便于处理大数
#define mp make_pair // 宏定义，简化make_pair的书写
#define pb emplace_back // 宏定义，简化emplace_back的书写，用于向容器中添加元素
#define rep(i, s, e) for (int i = s; i <= e; ++i) // 宏定义，简化for循环（从s到e）
#define drep(i, s, e) for (int i = s; i >= e; --i) // 宏定义，简化倒序for循环（从s到e）
#define file(a) freopen(#a ".in", "r", stdin), freopen(#a ".out", "w", stdout) // 宏定义，用于重定向输入输出到文件
#define pv(a) cout << #a << " = " << a << endl // 宏定义，用于打印变量名和变量值
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl // 宏定义，用于打印数组或容器的一部分
using pii = pair<int, int>; // 定义pii为int类型的pair，用于存储两个整数
const int N = 2e5 + 10; // 定义常量N，作为数组的最大大小
int read() {
int x = 0, f = 1;
char c = getchar(); // 定义结果变量x和符号变量f，使用getchar()读取一个字符
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -1; // 跳过非数字字符，检查负号
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - 48; // 计算数字的值
return x * f; // 如果检测到负号，则返回负值
}
int n, k, f[N], g[N], rk[N], ans; // 定义输入的n, k，数组f, g, rk以及结果变量ans
vector<pii> e[N]; // 定义数组e，每个元素是一个vector，存储pair<int, int>
// 函数dfs0：第一次深度优先搜索，计算每个节点作为根时的最大边权和
void dfs0(int u, int fa) {
vector<int> val; // 定义一个vector存储值
for (auto it : e[u]) { // 遍历与节点u相连的所有节点
int v = it.first, w = it.second; // 获取相邻节点的编号和边权
if (v != fa) { // 如果邻接节点不是父节点
dfs0(v, u); // 递归进行深度优先搜索
val.emplace_back(f[v]); // 将该节点的最大边权和加入到val中
} else
f[u] = w; // 否则，当前节点的最大边权和就是与父节点相连的边权
}
sort(val.begin(), val.end()); // 将val中的值进行排序
reverse(val.begin(), val.end()); // 将val中的值进行反转，使之按降序排列
int cnt = 0; // 定义计数变量cnt
for (int x : val) { // 遍历val中的每个值
if (cnt == k)
break; // 如果cnt达到k，则终止循环
f[u] += x, ++cnt; // 否则，将x加到f[u]上，并增加cnt
}
}
// 函数dfs1：第二次深度优先搜索，换根并更新最终答案
void dfs1(int u, int fa) {
int res = g[u]; // 定义变量res为g[u]，表示不包括u的其他部分的最大边权和
for (auto it : e[u]) { // 遍历与节点u相连的所有节点
int v = it.first, w = it.second; // 获取相邻节点的编号和边权
if (v != fa)
res += f[v]; // 如果邻接节点不是父节点，将f[v]加到res上
}
ans = max(ans, res); // 更新最终答案
vector<pii> val; // 定义一个vector存储pair
val.pb(mp(g[u], 0)); // 将g[u]和0作为一个pair加入到val中
for (auto it : e[u]) { // 遍历与节点u相连的所有节点
int v = it.first, w = it.second; // 获取相邻节点的编号和边权
if (v != fa)
val.pb(mp(f[v], v)); // 如果邻接节点不是父节点，将f[v]和v作为一个pair加入到val中
}
sort(val.begin(), val.end()); // 将val中的值进行排序
reverse(val.begin(), val.end()); // 将val中的值进行反转，使之按降序排列
int d = val.size(), s = 0; // 定义变量d为val的大小，s为0
rep(i, 0, d - 1) rk[val[i].second] = i; // 记录每个节点在val中的位置
rep(i, 0, min(d, k) - 1) s += val[i].first; // 计算s为val中前k个值的和
for (auto it : e[u]) { // 遍历与节点u相连的所有节点
int v = it.first, w = it.second; // 获取相邻节点的编号和边权
if (v == fa)
continue; // 如果邻接节点是父节点，则
}
}