假日住宿 题解

假日住宿

题目描述

给出一棵$N$节点的树，每个节点代表一个城市，每个城市有一个人，每个人离开自己的城市到另一个城市，每个城市只能有一个人，问这$N$个人移动距离和的最大值。

输入格式

输入的第一行包含一个整数 $T(1<=t<=10)$，表示测试用例的数量。每个测试用例包含几行。 第一行包含一个整数$2<=N<=10^5$ ，代表城市数。 然后接下来的行分别包含三个整数$X，Y，Z$ 意味着在城市$X$和城市$Y$之间有一条高速公路，其长度为$Z$。 您可以假设所有城市都已连接并且高速公路是双向的。

输出格式

输出每个样例中，所有人员的最大总行程。

样例

输入样例1

2 4 1 2 3 2 3 2 4 3 2 6 1 2 3 2 3 4 2 4 1 4 5 8 5 6 5

输出样例1

18 62

分析

这道题其实和树的重心有异曲同工的地方，虽然并不是求出重心来进行相关的操作，但是它所用的统计边数的方法与其十分类似。 此题关键不是在于人在怎么走，即不需要考虑人的移动，而是如何把边的作用发挥到最大。 考虑边的情况： 一条边连接了两个顶点，这两个顶点又可以拓展为两棵子树，如果想要最后的路程最长，那么就应该要更多的人去走这一条边，此时最多的人数就是左右两颗子树的点数中的较小者2w（左边的人走到右边，右边的人走到左边），点数就可以用与重心相同的方法计算。

核心代码

void dfs(LL fa, LL u) { s[u] = 1;//边界出口 || 初始只有自己一个节点 for (int i = 0; i < G[u].size(); i++) { LL v = G[u][i].v, w = G[u][i].w; if (v == fa) continue; dfs(u, v); s[u] += s[v];//累加点数 ans += w * 2 * min(s[v], n - s[v]);//即左右两颗子树的点数中的较小者 * 2 * w } }