267F
[ABC267F] Exactly K Steps 题解
[ABC267F] Exactly K Steps 题解 思路 首先发现，如果对于查询 \((u, k), k > 0\) 可行，那么对于 \((u, k - 1)\) 也一定可行，因为往回走一步就可以了，所以对于一个点可以找到离它最远的点，根据直径的结论，这个点一定是直径的端点之一。 为了方便做， ......
[题解]AT_abc267_f [ABC267F] Exactly K Steps
大家好，我是毒瘤，喜欢用玄学算法过题。 发现题解区没有这个做法，于是来发一篇。 思路 首先发现如果一个点对 \((u,v)\) 的距离为 \(d\)，那么在这棵树以 \(u\) 为根时，\(v\) 的深度为 \(d\)。 Code ......
[ABC267F] Exactly K Steps
多次询问 给出x,给出任意点y满足 dis(x,y)==m 以直径端点为根，dfs 可以发现 至少有一个y 在这个路径上 https://www.luogu.com.cn/record/130467795 ......
题解 ABC267F【Exactly K Steps】
Robin 有一棵树，他有 $m$ 次询问，每次询问他给你 $u,k$，你需要输出树上的一个节点 $v$ 满足 $dist(u,v)=k$，或者报告无解。
$dist(u,v)$ 表示树上 $u$ 到 $v$ 的最短路径的边数。$n\leq 10^5$ ......
「解题报告」[ABC267F] Exactly K Steps
「解题报告」[ABC267F] Exactly K Steps 大家好，我是个毒瘤，我非常喜欢没脑子做法，于是我就用点分治过了这个题 . 离线在每个点存下与其相关的询问 . 考虑如何计算跨重心的答案 . 记录下每个点在当前重心下的深度，同时开一个桶 \(t_{k, 0/1}\) 存下当前深度为 \( ......