Codeforces 932D - Tree

932D - Tree

思路：

树上倍增

anc[i][u]:u的2^i祖先

mx[i][u]:u到它的2^i祖先之间的最大值，不包括u

pre[i][u]:以u开始的递增序列的2^i祖先

sum[i][u]:以u开始递增序列从u到2^i祖先的和，不包括u

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=4e5+;

const ll INF=1e15;

int anc[][N],pre[][N];

ll sum[][N],w[N],mx[][N];

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    int q,cnt=,op;

    ll l,r,last=;

    w[]=INF;

    for(int i=;i<;i++)sum[i][]=sum[i][]=mx[i][]=mx[i][]=INF;

    cin>>q;

    while(q--){

        cin>>op>>l>>r;

        l^=last;

        r^=last;

        if(op==){

            anc[][++cnt]=l;

            w[cnt]=r;

            mx[][cnt]=w[l];

            for(int i=;i<;i++){

                anc[i][cnt]=anc[i-][anc[i-][cnt]];

                mx[i][cnt]=max(mx[i-][cnt],mx[i-][anc[i-][cnt]]);

            }

            int t=cnt;

            for(int i=;i>=;i--){

                if(mx[i][t]<w[cnt]){

                    t=anc[i][t];

                }

            }

            pre[][cnt]=anc[][t];

            sum[][cnt]=w[anc[][t]];

            for(int i=;i<;i++){

                pre[i][cnt]=pre[i-][pre[i-][cnt]];

                sum[i][cnt]=sum[i-][cnt]+sum[i-][pre[i-][cnt]];

            }

        }

        else{

            int ans=;

            if(w[l]<=r){

                ans=;

                r-=w[l];

                for(int i=;i>=;i--){

                    if(sum[i][l]<=r){

                        r-=sum[i][l];

                        l=pre[i][l];

                        ans+=<<i;

                    }

                }

            }

            last=ans;

            cout<<ans<<endl;

        }

    }

    return ;

}