c++ - Codeforces 关于二进制提升和 LCA 的问题

Question

最近，我在 Codeforces 上解决了这个问题，但我没有通过测试用例。我看不到测试用例，也看不到其他人的解决方案，因为这是一道道馆题。因为，我无法查看我的代码失败的测试用例，所以我需要一些帮助。我保证代码非常易读。问题主要是关于二进制提升和 LCA 计算。

可能知道，树懒生活在树上。因此，大卫有一只宠物树懒，当他解决编程问题时，他让它在他未加权的树上玩耍。有时，大卫会注意到他的树懒位于树中的特定节点上，并要求它移动到其他节点。

当然，树懒是出于善意，但可惜它只有足够的能量在大多数边缘移动。如果树懒需要穿过少于边缘才能到达节点，它会到达那里然后打个盹。否则，它会在退休前尽可能接近并闲置等待进一步消化。

树懒最终会去哪里？此外，由于这种情况经常发生，大卫希望您回答查询，每一个都类似的形式。

输入

第一行将包含一个整数，即树中的节点数。以下 -1 行将包含两个整数 和 ，描述树中的边。这些边将形成一棵树。

之后，将有一行包含一个整数 ，即大卫激励他的树懒移动的次数。接下来的行，每行包含三个整数 、 和 ：树懒开始的节点，大卫要求树懒移动到的节点，以及树懒开始时的能量。

int LOGN = 19;
int n;
int timer = 0;
vector<int> adj[300005];
bool vis[300005];
int p[300005], tin[300005], tout[300005];
vector<int> d(300005,0);
int dp[300005][20];

void dfs(int v, int parent)
{
    tin[v] = ++timer;
    if (parent != -1)
        d[v] = d[parent] + 1;
    p[v] = parent;
    dp[v][0] = parent;
    for (int i = 1; i < LOGN; i++){
        if (dp[v][i &mdash; 1] == -1)
            dp[v][i] = -1;
        else
            dp[v][i] = dp[dp[v][i &mdash; 1]][i &mdash; 1];
    }
    for (auto u : adj[v]){
        if (u != parent)
            dfs(u, v);
    }
    tout[v] = ++timer;
}
bool isAncestor(int p, int c){ // check if p is ancestor of c
    return (tin[p] <= tin[c] && tout[p] >= tout[c]);
}
int lift(int v, int steps) //find the y-th ancestor of x
{
    for (int i = 0; i < 19; ++i){
        if ((1 << i) & steps){
            v = dp[v][i];
            if (v == -1)
                return -1;
            steps -= (1 << i);
        }
    }
    return v;
}
int LCA(int u, int v)
{
    if (isAncestor(u, v))
        return u;
    if (isAncestor(v, u))
        return v;
    for (int i = 18; i >= 0; i--)
    {
        if (dp[u][i] == -1)// -1 should not be passed
            continue;
        if (!isAncestor(dp[u][i], v))
            u = dp[u][i];
    }
    return dp[u][0];
}
void solve()
{
    cin>>n;
    timer=0;
    for(int i=0;i<n-1;i++){// Input
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(0,-1);
    tout[0]=++timer;
    int q;
    cin>>q;
    for(int z=0;z<q;z++){
        int u,v,energy;
        cin>>u>>v>>energy;
        u--;v--;
        if(isAncestor(u,v))// u is ancestor of v
        {
            if(d[v]-d[u]<=energy)// reachable
                cout<<v+1<<endl;
            else{// midway: lift
                int res=lift(v,energy);
                cout<<res+1<<endl;
            }           
        }
        else if(isAncestor(v,u))// v is ancestor of u
        {
            if(d[u]-d[v]<=energy)// reachable
                cout<<v+1<<endl;
            else{/// midway: lift
                int res=lift(u,d[u]-d[v]-energy);
                cout<<res+1<<endl;
            }       
        }
        else{
            int lca=LCA(u,v);
            int dist=d[u]+d[v]-2*d[lca];
            if(energy>=dist)
                cout<<v+1<<endl;
            else{   
                // find vertex of the path from u to v with distance of energy from u
                int dist1=d[u]-d[lca];
                int dist2=d[v]-d[lca];
                // lies on the path from u to LCA
                if(energy<=dist1){
                    int res=lift(u,energy)+1;
                    cout<<res<<endl;
                }
                // lies on the path from LCA to v
                else{
                    int rem=energy-dist1;
                    dist2-=rem;
                    int res=lift(v,dist2)+1;
                    cout<<res<<endl;
                }   
            }
        }           
    }
}
signed main() 
{ 
    FAST;
    solve();
    return 0; 
} 

标签： c++algorithm