题目链接 https://www.luogu.com.cn/problem/P3379 解题思路 ST表 + 欧拉序 。通过欧拉序会发现根结点总在中间,而根结点是该段序列深度最小的点。因此两个点的LCA,就是在该序列上两个点第一次出现的区间内深度最小的那个点。 细节见代码,主要是注意下标含义。 AC代码 #include<bits/stdc++.h> using namespace std; const int N=5e5+100; int n,m,rt,Time,a,b; int path[N<<1],pos[N<<1][20],dp[N],in[N],...