首页 > 聚会
开通博客写题解
头像 ThinkofBlank
发表于 2020-04-19 19:37:00
这道题莫名眼熟，于是马上猜到了结论： 对于一棵树中，要求到三个点x,y,z总距离最小的点，那么，这个点一定是 lca(x,y),lca(x,z),lca(y,z)这三个点中的一个（一开始我还算了lca(x,y,z),后来发现好像不用。。。） 所以，我们可以打个lca，每次再比较下到哪个点距离最小即可 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Fyyg
发表于 2020-04-19 15:00:11
这道题，我一看就蒙了，竟然考这样赤裸裸的LCA，我也是醉了。。。最近公共祖先（LCA）让我们轻而易举地想到了Tarjan+倍增算法来使用。本人代码如下：#include<bits/stdc++.h>using namespace std;const int N=500003,L=19;i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”