51Nod-1737-配对

ACM模版

描述

题解

这个问题实际上是找树的重心，只要找到重心 dfs 遍历一遍求各个路径的权值，各点到重心的权值之和就是最大距离总和。至于怎么找重心，其实也是一遍 dfs，有固定的模版，代码不难理解。说以这个问题只需要先 dfs 一遍找到树的重心，然后再 dfs_ 一遍求各个点到重心的路径权值，最后，累加各个点的路径权值即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>#define pb push_back
#define mp make_pairusing namespace std;typedef long long ll;
typedef pair<int, int> pll;const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;int n;
ll wr[MAXN];    //  wr[i] i 到重心 zx 的带权路径长度/*  树的重心*  初始化 vis[] son[] 为 0*  初始化 sz 为 INF*/
int zx, sz;
int son[MAXN], vis[MAXN];
vector<pll> edge[MAXN];void init()
{for (int i = 1; i <= n; i++){edge[i].clear();}memset(vis, 0, sizeof(vis));memset(wr, 0, sizeof(wr));sz = INF;zx = -1;
}void dfs(int r)
{vis[r] = 1;son[r] = 0;int tmp = 0;for (int i = 0; i < edge[r].size(); i++){int v = edge[r][i].second;if (!vis[v]){dfs(v);son[r] += son[v] + 1;tmp = max(tmp, son[v] + 1);}}tmp = max(tmp, n - son[r] - 1);if (tmp < sz){zx = r;sz = tmp;}
}void dfs_(int x)
{vis[x] = 1;for (int i = 0; i < edge[x].size(); i++){int v = edge[x][i].second;if (!vis[v]){wr[v] = wr[x] + edge[x][i].first;dfs_(v);}}
}int main()
{while (~scanf("%d", &n)){init();for (int i = 0; i < n - 1; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);edge[u].pb(mp(w, v));edge[v].pb(mp(w, u));}dfs(1);memset(vis, 0, sizeof(vis));dfs_(zx);ll ans = 0;for (int i = 1; i <= n; i++){ans += wr[i];}printf("%lld\n", ans);}return 0;
}

参考

《树的重心》