9481
P9481 [NOI2023] 贸易 题解
[题目链接](https://www.luogu.com.cn/problem/P9481) 题目要求我们求出任意两点间最短路径之和，由于图比较特殊，除树边外只有祖先到其子树内的边，我们首先考虑最短路径有没有什么特殊性质。 注意到两点之间的最短路分为一下三种： 1. 节点到其祖先的最短路：直接沿着树 ......
P9481 [NOI2023] 贸易
不好评价题。 容易知道在该题目条件下 $dis[u\to v]=dis[u\to\text{LCA}(u,v)]+dis[\text{LCA}(u,v)\to v]$。其中 $dis[u\to\text{LCA}(u,v)]$ 是 $u$ 一直往父亲跳，容易预处理。现在难点在于处理出所有 $dis[ ......