NAPC

这道题我看大家都用 dijkstra 啊，惊恐，这里提供一种换根 dp 的写法。 两点间最短路径，那一定是 LCA 没错了。用一遍 dfs 求出根节点到每个点的距离，记为 \(dist\)。那么 \(u,v\) 间最短路径长度就是 \(dist_u+dist_v-dist_{\operatornam ......

P9432 [NAPC-#1] rStage5 - Hard Conveyors 感谢此题让我知道了 Dijkstra 的一种新用法。 题意： 给定一棵 \(n\) 个节点的无根树以及树上的 \(k\) 个关键节点，给定边的长度。有 \(q\) 次询问，每次给出 \(s,t\)，问从 \(s\) 到 ......

这个人赛时只过了这题，但是同学 @[sinsop90](https://www.luogu.com.cn/user/141599) 赛时只没过这题，怎么会是呢？ 考虑到 $s,t$ 之间路径必须经过关键点，假设这个关键点为 $k$，那么路径形式一定是 $s\to k\to t$（废话）。 画一下图发 ......

[传送门](https://www.luogu.com.cn/problem/P9431) ~~这个人赛时看错了几次题目导致样例调了 1h。~~ ## $Sol1: n \leqslant 10, T \leqslant 10$ 乱搞分。 枚举跳跃的顺序，判断可不可行，最后取最大值，复杂度 $O(( ......