树距离
题意
对于一个 \(N\) 个节点，\(N−1\) 条无向边组成的树，我们规定两点之间的距离 \(dis(u,v)\) 为两点唯一简单路径上的最小边权。给定树的结构，对于树上每一个节点 \(1\le i\le N\), 请计算出 
。特别的，我们定义 \(dis(i,i)=0\)。
思路
并查集，然后用于类似题相同的思路，可以记录生成树，然后在便利生成树时，记录答案即可。
code
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MaxN = 2e5 + 10;
struct S {
int a, b, w;
} e[MaxN];
int fa[MaxN], n, m, cnt;
long long c[MaxN], ans[MaxN];
vector<int> g[MaxN];
int fr(int x) {
return (fa[x] < 0 ? x : fa[x] = fr(fa[x]));
}
void Merge(int x, int y, int w) {
x = fr(x), y = fr(y);
if (x == y) {
return;
}
if (fa[x] < fa[y]) {
swap(x, y);
}
g[y].push_back(x);
cnt++;
c[y] += -1ll * fa[x] * w, c[x] += -1ll * fa[y] * w - c[y];
fa[y] += fa[x], fa[x] = y;
}
void DFS(int x, long long sum) {
ans[x] = sum;
for (int i : g[x]) {
DFS(i, sum + c[i]);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
freopen("treeDis.in", "r", stdin);
freopen("treeDis.out", "w", stdout);
cin >> n;
fill(fa + 1, fa + n + 1, -1);
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[i] = {u, v, w};
}
sort(e + 1, e + n, [](S a, S b){return a.w > b.w;});
for (int i = 1; i < n; i++) {
Merge(e[i].a, e[i].b, e[i].w);
}
for (int i = 1; i <= n; i++) {
if (fa[i] < 0) {
DFS(i, c[i]);
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
return 0;
}