其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。如上图中，
若医院建在1 处，则距离和=4+12+2*20+2*40=136；若医院建在3 处，则距离和=4*2+13+20+40=81……
对于每个根可以很容易的通过一遍dfs获得答案
然后考虑换根，对于根u v 将根从u换到v后v子树中的每个节点距离新根的距离都要减一，对于原根的除v外的子树的距离都要加一， 实际上等价于减去一遍子v树的总权值，加上一遍除v外子树的权值。然后更新答案即可
/* Zeolim - An AC a day keeps the bug away */ //#pragma GCC optimize(2) //#pragma GCC ("-W1,--stack=128000000") #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define fr(x, y, z) for(int x = y; x < z; ++x) #define pb(x) push_back(x) #define mem(x, y) memset(x, y, sizeof(x)) typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef std::pair <int, int> pii; typedef std::vector <int> vi; //typedef __int128 ill; const ld PI = acos(-1.0); const ld E = exp(1.0); const ll INF = 0x3f3f3f3f3f3f3f3f; const ll MOD = 386910137; const ull P = 13331; const int MAXN = 1e6 + 100; vector <int> edge[MAXN]; ll val[MAXN] = {0}; ll rans[MAXN] = {0}; ll size[MAXN] = {0}; ll n; void dfs(int now, int fa, int deep) { size[now] += val[now]; rans[1] += val[now] * deep; for(auto x : edge[now]) { if(x != fa) { dfs(x, now, deep + 1); size[now] += size[x]; } } } void gao(int now, int fa) { for(auto x : edge[now]) { if(x != fa) { rans[x] = rans[now]; rans[x] -= size[x]; rans[x] += size[1] - size[x]; gao(x, now); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("d:\out.txt","w",stdout); //freopen("d:\in.txt","r",stdin); cin >> n; int ls, rs; for(int i = 1; i <= n; ++i) { cin >> val[i] >> ls >> rs; if(ls) edge[i].push_back(ls), edge[ls].push_back(i); if(rs) edge[i].push_back(rs), edge[rs].push_back(i); } dfs(1, 0, 0); gao(1, 0); ll ans = INF; for(int i = 1; i <= n; ++i) { ans = min(ans, rans[i]); } cout << ans << '\n'; return 0; }
