一棵 n 点的树，你可以询问 dis(u,v)+dis(v,w)+dis(u,w)（u,v,w 两两不同）3n 次，询问两次 u 是否在 v 到 w 的路径上。求任意一条直径的两端点。
显然三个点的查询结果是三点间路径并的长度的两倍。
找直径，要求从一个点出发找最远点。
感知一下。固定一条链 (u,v) 向外询问 u,v,i，得到 i 到链的距离，显然链越短误差越小，于是先考虑在链上找一条边。
先得到链 (u,v) 上所有的点。用一个 n。
一条歪路
随机选链上一个点 x，问出 u 到 x 的点，递归 u,x，期望两倍链长。实际上不必找支点。易知查询 u,i,j 的结果是 max(dis(u,i),dis(u,j))。只要找到链上离 u 最远的点，它与 v 就是一条边。若链上点的序列是 a，查询 u,a(i),a(i+1)，找最大值的位置即可。用一倍链长。
接下来可以 n-链长 找到离边的最远点 ans1。只剩一个 n 能用了。
枚举直径另一端。如果相对红边处于异侧是容易的。
否则设图中的 a,b,c，询问得到 a+b+c，而 a+c,b+c 可以在问 ans1 时预处理。加加减减就得到 a+b 即两点间距离了。
总结：真 tm 怎么做都可以，赛时完全不发挥导致的。
https://qoj.ac/submission/860816
标签：一条,链长,询问,查询,2025,PKUWC,D2T1,最远,dis From： https://www.cnblogs.com/Zaunese/p/18680716