【做题笔记】NOI2023 D2T1
Problem
一个共 \(n\) 层的内向满二叉树，给定 \(m\) 个前向边（即往子树走的边），边有非负权，问所有可以从 \(u\) 通向 \(v\) 的点对 \((u,v)\) 的最短路长度之和。\(n\le18\)，\(m\le2\times10^5\)。
Preface
D1T1 是我基本上独立想出的，这个题是补的。
我也想拿牌子。
Solution
考虑一个点 \(u\) 通向 \(v\) 的方式。
如果 \(v\) 在 \(u\) 的子树内，那么显然只会走子树里面的边走到。
否则，可以证明是先从 \(u\) 走到 \(fa_u\)，再走 \(fa_u\) 到 \(v\) 的最短路。
第一种是好处理的。对于每个点 \(u\) 在其子树内跑 Dijkstra。下证明复杂度。
首先 Dijkstra 的复杂度为 \(O(|E|\log|V|+|V|)\)。由于 \(|E|\) 可能很小，所以后者不能忽略。对于距离根为 \(0\le i<n\) 的 \(2^i\) 个点，所有 \(|E|\) 的和显然是 \(\le m\) 的，而 \(|V|=2^{n-i}-1\)，则 \(\sum(|E|\log|V|+|V|)<\sum\limits_{i=0}^{n-1}m(n-i)+2^{n-i}\cdot 2^i=O(n2^n+nm)\)。所以这一部分复杂度为 \(O(n2^n+nm)\)。