LCA求助,悬赏一个关注
  • 板块学术版
  • 楼主chenruikai
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/7 23:00
  • 上次更新2024/7/8 09:28:14
查看原帖
LCA求助,悬赏一个关注
1041549
chenruikai楼主2024/7/7 23:00

哪位大佬帮忙看看下面这段在线求 LCALCA 的代码错哪了

题目:P3379P3379,3 ACAC,其余皆 RERE

#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;
}
2024/7/7 23:00
加载中...