You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

82 lines
2.4 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2e5 + 10, M = N << 1;
int n, du[N];
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int f[N], g[N];
// 以1号点为根 由子推父,先递归,再统计
void dfs1(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs1(v, u);
if (du[v] == 1)
f[u] += w[i];
// 如果v是叶子,u->v的边权可以加到f[u]中
// 代表着u的最大消化能力,比如样例中的4号节点它连接着3和5两个节点边权分别是5,10
// 所以它的最大消化能力=5+10=15
else // 如下对方节点不是叶子比如1号节点需要取f(1)=min(w[u][v],f(4))
// 当然别忘了1也可能有其它的子节点需要要使用f[1]+=
// f[u]:表示向底向上统计来的1号节点的消化能力
f[u] += min(f[v], w[i]);
}
}
// 自顶向下,由父推子,先计算,后递归
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
if (du[u] == 1) // 如果u是叶子 那么w[v][u]=w[i]是可以火力全开的
g[v] = f[v] + w[i];
else // 如果u不是叶子
g[v] = f[v] + min(g[u] - min(f[v], w[i]), w[i]);
// 先计算再递归
dfs2(v, u);
}
}
int main() {
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
int T;
cin >> T;
while (T--) {
// 初始化链式前向星
memset(h, -1, sizeof h);
idx = 0;
memset(du, 0, sizeof du);
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
cin >> n;
int a, b, c;
for (int i = 1; i < n; i++) { // 树n-1条无向边
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
du[a]++, du[b]++; // 记录入度,无向图就不谈入度和出度了
}
// 第一遍dfs
dfs1(1, 0);
g[1] = f[1];
// 第二遍dfs
dfs2(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, g[i]);
cout << ans << endl;
}
return 0;
}