2020.03.22日常总结

$\color{green}{\text{洛谷P1395\ \ \ \ \ 会议}}$洛谷P1395     会议

---

$\color{blue}{\text{【题意】：}}$【题意】：

• 给定一棵无根树，定义 $u$u 到 $v$v 的距离为简单路径 $(u,v)$(u,v) 上的边的数量。我们把它记为 $T_{u,v}$Tu,v​。
• 定义以 $u$u 为该无根树时的花费为 $\sum\limits_{i=1}^{n} T_{u,i}$i=1∑n​Tu,i​。即所有点到根 $u$u 的距离和。我们把它记为 $G_u$Gu​。
• 求一个点 $u$u，使得 $G_u$Gu​ 最小。输出 $u$u 和 $G_u$Gu​。如有多解，则输出最小的 $u$u。
• 对于 $100 \%$100% 的数据，$1\leq n \leq 5 \times 10^4$1≤n≤5×104。

---

$\color{blue}{\text{【思路】：}}$【思路】：

对于无根树类的题目，我们可以先指定一个点当作根。然后再考虑。

具体地，我们先求出以 $1$1 为根时以每个点 $u$u 为根的子树的大小 $f_u$fu​ 及 $G_1$G1​。

考虑根从点 $u$u 转移到它的一个儿子 $v$v 时总花费的变化量。可以发现，有等量关系 $G_v=G_u - f_v + (n - f_v)$Gv​=Gu​−fv​+(n−fv​)。

什么意思？即 $v$v 的所有儿子到根的距离都减少了 $1$1，但是所有不是 $v$v 的儿子到根的距离都增加了 $1$1。我们可以根据这个来算出所有的 $G$G。可以配图理解 （图丑请原谅）。

总的时间复杂度为 $O(n)$O(n)。可以通过更大的数据（比如 $1 \times 10^6$1×106）。

---

$\color{blue}{\text{【代码】：}}$【代码】：