Minecraft OI Round 2 D 题解
一只书虫仔
·
·
题解
已获得出题人授权。
\large\texttt{Subtask1:\ 3\ pts}
读题分，枚举所有的 (u,v)，然后花费 O(N) 的时间计算 u,v 之间链上的点权和和边权和，统计答案即可。
时间复杂度 O(N^3)。
\large\texttt{Subtask2:\ 6\ pts}
我们延续上面的思路，枚举所有的 (u,v)，然后统计答案。
但是统计答案可以优化到 O(\log N)。我们算出每个节点到根节点路径上的边权和和点权和，即树上前缀和，一遍 DFS 即可。对于两个点 u,v，我们求出它们的 LCA，然后用前缀和求出 u,v 两点路径上的边权和与点权和。
时间复杂度 O(N^2\log N)。
\large\texttt{Subtask3:\ 11\ pts}
拿到这个 Subtask 有两种方式。
- 考虑优化 Subtask 2 的方法，什么倍增树剖 LCA 太慢了，我们用 tarjan 算法可以优化到线性。不过 tarjan 算法常数偏大，轻微卡常。
- 换一种思路，我们枚举一个端点，然后以它为根节点进行 DFS。DFS 到的每个节点的树上边权前缀和和点权前缀和的乘积统计到答案中。代码简单，常数优秀。
时间复杂度 O(N^2)。
\large\texttt{Subtask4:\ 12\ pts}
菊花图。
考虑链的形态就两种情况。长度为 1 的链和长度为 2 的链。长度为 1 的链就是一条边，直接枚举边统计。长度为 2 的链肯定经过中心点，枚举一个端点对另一个端点算贡献即可。
时间复杂度 O(N)。
\large\texttt{Subtask5:\ 13\ pts}
链。
不失一般性，我们假设链的形态是 1-2-3-\dots-N。
考虑对每条边算贡献。对于一条边，端点为 i,i+1。左边在 [1,i] 右边在 [i+1,N] 的操作会经过该边。这条边一共会被算 i\times(N-i) 次。对于点权，我们看成点 i 要算 V_i 次即可
时间复杂度 O(N)。
\large\texttt{Subtask6:\ 25\ pts}
我们要统计所有路径的贡献，点分治是个不错的选择。
考虑将两条半链 A,B 拼起来。完整的链的贡献为
\left(\sum W_A+\sum W_B\right)\times \left(\sum V_A+\sum V_B\right)
乘一下得到
\sum W_A\times \sum V_A+\sum W_A\times \sum V_B+ \sum W_B\times \sum V_A+\sum W_B\times \sum V_B
开几个变量分别记录 \sum W 和 \sum V 的前缀和即可。
时间复杂度 O(N \log N)。
\large\texttt{Subtask7:\ 35\ pts}
你认为结束了？并没有，因为我们有更优秀的做法。
延续链的思路，我们对每条边算贡献。我们称一条边两侧为左右两侧。
以边两个端点为根分别 DFS，不经过当前正在统计的边。记 Val_i 为节点 i 的子树大小和点权的乘积。则这条边的贡献为左侧所有点的 Val 的和与右侧子树大小的乘积加右侧所有点的 Val 的和与左侧子树大小的乘积。别忘了还要乘以自身的边权。
但是每次都要 DFS 不是沦为和暴力老哥同分吗。没错，这里我们需要换根 DP。两次 DFS，在第二次 DFS 的时候同时统计所有边的答案。
时间复杂度 O(N)。