lxhgww的奇思妙想 长链剖分板子

https://vijos.org/d/Bashu_OIers/p/5a79a3e1d3d8a103be7e2b81

求k级祖先,预处理nlogn,查询o1

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

//#include <bits/extc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define mt make_tuple

//#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

//#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define sqr(x) ((x)*(x))

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define ull unsigned long long

#define bpc __builtin_popcount

#define base 1000000000000000000ll

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

#define mr mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=mul(ans,a,c);a=mul(a,a,c),b>>=1;}return ans;}

using namespace std;

//using namespace __gnu_pbds;

const ld pi=acos(-1);

const ull ba=233;

const db eps=1e-5;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=300000+10,maxn=5000000+10,inf=0x3f3f3f3f;

vi v[N],ch[N],rch[N];

int fa[N][20],dep[N],son[N],mdep[N],top[N],highbit[N];

void dfs1(int u,int f,int de)

{

    fa[u][0]=f;dep[u]=mdep[u]=de;

    for(int x:v[u])if(x!=f)

    {

        dfs1(x,u,de+1);

        if(son[u]==-1||mdep[x]>mdep[son[u]])son[u]=x,mdep[u]=mdep[x];

    }

}

void dfs2(int u,int f,int tp)

{

    top[u]=tp;ch[tp].pb(u);

    if(son[u]!=-1)dfs2(son[u],u,tp);

    for(int x:v[u])if(x!=f&&x!=son[u])dfs2(x,u,x);

}

int query(int x,int k,int id)

{

    if(dep[x]<k)return 0;

    if(k==0)return x;

    int y=fa[x][highbit[k]],len=dep[y]-dep[top[y]];

    k-=(1<<highbit[k]);

    if(k<=len)return ch[top[y]][len-k];

    else return rch[top[y]][k-len];

}

int gao(int x)

{

    int num=0;

    while(x)x/=2,num++;

    return num-1;

}

int main()

{

    memset(son,-1,sizeof son);

    int n;scanf("%d",&n);

    for(int i=1;i<n;i++)

    {

        highbit[i]=gao(i);

        int a,b;scanf("%d%d",&a,&b);

        v[a].pb(b),v[b].pb(a);

    }

    highbit[n]=gao(n);

    dfs1(1,0,0);dfs2(1,0,1);

    for(int i=1;i<=n;i++)

    {

        int now=i;

        for(int j=0;j<ch[i].size();j++)rch[i].pb(now),now=fa[now][0];

    }

    for(int i=1;i<20;i++)for(int j=1;j<=n;j++)

        fa[j][i]=fa[fa[j][i-1]][i-1];

    int m,ans=0;scanf("%d",&m);

    while(m--)

    {

        int a,b;scanf("%d%d",&a,&b);

        a^=ans,b^=ans;

        printf("%d\n",ans=query(a,b,m));

    }

    return 0;

}

/********************

********************/