哪位大佬帮忙看看下面这段在线求 LCA 的代码错哪了
题目:P3379,3 AC,其余皆 RE
#include <bits/stdc++.h>
using namespace std;
#define debug 0
#define puterr(...) if(debug)printf(__VA_ARGS__)
#define debugpart if(debug)
#define unclear -1
struct cell
{
int deep;
vector <int> fapos;
vector <int> con;
};
cell point[500005];
int log_num[21] = {0 , 0 , 1 , 1 , 2 , 2 , 2 , 2 , 3 ,
3 , 3 , 3 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4};
int pointnum , quenum , root;
void addedge(int pos1 , int pos2)
{
point[pos1].con.push_back(pos2);
point[pos2].con.push_back(pos1);
}
vector <int> fapos_wait;
void compute_fapos(int pos)
{
point[pos].fapos.clear();
for(unsigned long long int power = 1;
power <= fapos_wait.size();power <<= 1)
point[pos].fapos.push_back(fapos_wait[fapos_wait.size() - power]);
fapos_wait.push_back(pos);
for(int nextpos : point[pos].con)
{
if(point[nextpos].deep == unclear)
{
point[nextpos].deep = point[pos].deep + 1;
compute_fapos(nextpos);
}
}
fapos_wait.erase(fapos_wait.end() - 1);
}
#define lowbit(a) ((a) & (-(a)))
int compute_lca(int pos1 , int pos2)
{
if(pos1 == pos2)return pos1;
if(point[pos1].deep < point[pos2].deep)
swap(pos1 , pos2);
for(int beta = point[pos1].deep - point[pos2].deep;
beta > 0;beta -= lowbit(beta))
pos1 = point[pos1].fapos[log_num[lowbit(beta)]];
// puterr("pos1 = %d , pos2 = %d\n" , pos1 , pos2);
if(pos1 == pos2)return pos1;
int ans = 0;
while(true)
{
int l = 0 , r = point[pos1].fapos.size() - 1;
int mid;
while(l < r)
{
mid = (l + r + 1) >> 1;
if(point[pos1].fapos[mid] == point[pos2].fapos[mid])
r = mid - 1;
else l = mid;
}
pos1 = point[pos1].fapos[l];
pos2 = point[pos2].fapos[l];
if(pos1 == pos2)
{
ans = pos1;
break;
}
if(point[pos1].fapos[0] == point[pos2].fapos[0])
{
ans = point[pos1].fapos[0];
break;
}
}
return ans;
}
int main()
{
cin >> pointnum >> quenum >> root;
root--;
int pos1 , pos2;
for(int i = 0;i < pointnum - 1;i++)
{
cin >> pos1 >> pos2;
addedge(pos1 - 1 , pos2 - 1);
}
for(int i = 0;i < pointnum;i++)
point[i].deep = unclear;
point[root].deep = 0;
compute_fapos(root);
for(int i = 0;i < quenum;i++)
{
cin >> pos1 >> pos2;
cout << compute_lca(pos1 - 1 , pos2 - 1) + 1 << endl;
}
return 0;
}