【题目来源】
洛谷：[P2052 NOI2011] 道路修建 - 洛谷
【题目描述】
在 W 星球上有 \(n\) 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 \(n - 1\) 条双向道路。
每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 \(2\) 个、\(4\) 个国家，如果该道路长度为 \(1\)，则费用为 \(1×|2 - 4|=2\)。图中圆圈里的数字表示国家的编号。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。
【输入】
输入的第一行包含一个整数 \(n\)，表示 W 星球上的国家的数量，国家从 \(1\) 到 \(n\) 编号。
接下来 \(n - 1\) 行描述道路建设情况，其中第 \(i\) 行包含三个整数 \(a_i\)，\(b_i\) 和 \(c_i\)，表示第 \(i\) 条双向道路修建在 \(a_i\) 与 \(b_i\) 两个国家之间，长度为 \(c_i\)。
【输出】
输出一个整数，表示修建所有道路所需要的总费用。
【输入样例】
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
【输出样例】
20
【算法标签】
《洛谷 P2052 道路修建》 #树形数据结构# #广度优先搜索BFS# #深度优先搜索DFS# #NOI# #2011#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long // 将int定义为long long类型
const int N = 1000005, M = N * 2; // N: 最大节点数, M: 最大边数(双向边)int n; // 节点数
int cnt[N]; // cnt[u]: 以u为根的子树大小
int ans; // 最终答案
int h[N]; // 邻接表头
int e[M]; // 边的终点
int w[M]; // 边的权重
int ne[M]; // 下一条边
int idx; // 边计数器// 添加边
void add(int a, int b, int c)
{e[idx] = b; // 存储终点w[idx] = c; // 存储边权ne[idx] = h[a]; // 插入到链表头部h[a] = idx++; // 更新头指针
}// 第一次DFS：计算每个节点的子树大小
void dfs(int u, int fa)
{cnt[u] = 1; // 初始化，包含自己// 遍历所有邻接点for (int i = h[u]; i != -1; i = ne[i]){int j = e[i]; // 子节点if (j == fa) continue; // 跳过父节点dfs(j, u); // 递归处理子节点cnt[u] += cnt[j]; // 累加子树的节点数}
}// 第二次DFS：计算总贡献
void dfs2(int u, int fa)
{// 遍历所有邻接点for (int i = h[u]; i != -1; i = ne[i]){int j = e[i]; // 子节点if (j == fa) continue; // 跳过父节点// 计算边(u, j)的贡献// cnt[j]: 子树j的节点数// n - cnt[j]: 另一部分的节点数// 两部分的差值乘以边权ans += w[i] * abs(cnt[j] - (n - cnt[j]));// 递归处理子节点dfs2(j, u);}
}signed main() // 因为使用了#define int long long，所以用signed main
{// 初始化邻接表memset(h, -1, sizeof(h));// 输入节点数cin >> n;// 输入n-1条边for (int i = 1; i < n; i++){int u, v, w;// 使用scanf加速输入scanf("%d%d%d", &u, &v, &w);// 添加双向边add(u, v, w);add(v, u, w);}// 第一次DFS：计算子树大小dfs(1, 0);// 第二次DFS：计算总贡献dfs2(1, 0);// 输出结果cout << ans << endl;return 0;
}
【运行结果】
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
20