传送 NOI 2026

[NOI 2026] 传送

NOI2026D1T1 线段：做干净的奥赛。

题目链接： [NOI 2026] 传送 。

题目描述：

一颗 $n$ 个点的树。有 $m$ 个询问，每次询问从 $x$ 到 $y$ 游走期望耗时有限且最短的时间为多少。对于一个节点 $i$ ，一次游走耗时一秒。每一次游走你可以选择移动到相邻节点或选择绝对随机的传送到一个点。

$n\le5\times10^5,m\le10^6$ 。

简单题。

容易发现对于某一次询问 $x\to y$ ，总有一个 $k$ 使得距离 $y$ 不超过 $k$ 的所有点都会选择向 $y$ 前进，其余点选择随机传送。并且这个 $k$ 具有单调性，可以二分求出。对于树上 $k$ 邻域数点，可以使用点分树在 $O(\log n)$ 求解。总复杂度 $O(n\log^2n+q)$ 。

代码不放了。