「DROI」Round 1 距离 题解

· · 题解

原题链接

前言

作为验题人，感觉是挺有意思的一道题，从题目转化到完成这道题都是循序渐进的。这道题也不怎么卡常，跑下来最慢的点差不多 1.1s。

这里分享一种不用树形 DP 的做法。 （wtcl）

题意

给定一棵 n 个节点的树，求每个点被直径穿过的次数的 k 次方之和。

分析

下面有两个简单的结论。

结论 1： 一定存在一个点 p 被所有直径穿过。

证明：考虑反证法。假如现在有两条直径 a \rightarrow b 和 c \rightarrow d 不相交，且分别穿过 p_1 和 p_2 (可以结合下图，灵魂画手)。那么路径 b \rightarrow p_1 \rightarrow p_2 \rightarrow c 显然更长，所以路径 a \rightarrow b 和 c \rightarrow d 不是直径。因此没有两条直径不相交，所有直径一定交于一点。

UPD：我的证明比较感性，更完整的证明可以参考这个。

结论 2： 所有直径都是由从 p 出发的最长链和次长链组成。（ p 是被所有直径穿过的一点）

证明显然。

现在我们再来看这道题（下面的分析均在树有最长链和次长链的情况下）。首先找到点 p，以 p 为树根，记录每个点 u 的最长链个数和长度分别为 cnt_u 和 len_u，特别地，记录 p 的最长链和次长链的个数分别为 num_1 和 num_2。

那么怎么统计每个点被直径穿过的次数呢？我们考虑所有的叶节点，如果一个叶节点在直径上，要么是在最长链上，与所有次长链构成直径，它的答案就是 num_2；要么是在次长链上，同理，它的答案就是 num_1。最后向上合并答案，点 p 的答案算重复了，要除以 2。

再考虑一种特殊的情况：这棵树只有最长链。

结合下图，在最长链上的叶节点的答案就是 num_1 - cnt_u。

至此，每一个点被直径穿过的次数都被求了出来，按照题目求 k 次方和就行了。

时空复杂度均为 O(n)，是优秀的线性做法。

UPD：忘记了一个特殊情况被 hack 了，感谢。如果还有 hack 数据可以私信我。（时隔太久，已经快要忘记当初写的什么东西了）

还有一种特殊情况就是只有最长链且对应的 p 的儿子只有一个，那么最长链上的叶节点的答案就是 1，向上合并就行了，且 p 的答案没有算重复，不用除以 2。

注意

  1. 取模要勤快，不然后面的大数据会爆掉。
  2. 分情况讨论答案。

Code

由于代码又丑又长，就贴在剪贴板了。有什么错误还请 dalao 在评论区指出。