题解

思路概述

• 新加入的点总是沿着某个结点 $u$ 向下接出一条链，且新编号连续。因此整棵树可以看作由若干条“链段”拼接而成：每条链段是一段连续编号 [L,R]，它的第一个结点有一个父亲（位于上一条链段中），其它结点都只是简单的儿子。
• 我们以链段为单位维护树形结构。为每个链段记录：起止编号 st/ed、该链段上首结点在原树中的深度 dep，链段的层数 chdep，以及指向父链段的倍增祖先 fa[k]。由于所有链段是按照创建顺序加入的，使用一个按 st 排序的有序集合即可在 $O(\log n)$ 内找到任意编号属于哪条链段。
• 查询 dig(u,v) 时，先定位两个结点所在的链段，然后在链段树上做 LCA。设链段 LCA 为 c，则 $u,v$ 的距离可拆成三部分：从 $u$ 向上爬到 c 所在链段，从 $v$ 向上爬到 c，以及在 c 内部的距离。我们可以通过 jumpDEP 函数计算在链段树上上跳时距离 c 还差多少深度，再判断中点在谁的半边，并调用 KthPar 在链段中向上走指定步数得到答案节点。

实现细节

• getchn(x) 使用有序集合 R 找到以 st 为关键字的小于等于 x 的最大链段，从而确定编号属于哪个区间。
• chnLCA 对链段树做倍增 LCA。jumpDEP 用来计算“若中点位于祖先链段中，本链段内最多还能上跳多少层”，KthPar 则在链段树与链段内部双重跳跃，支持在 $O(\log n)$ 时间求出沿树向上第 $k$ 个结点。
• 每次 path u s 新建一条链段时，先确定其父链段，再补齐所有倍增祖先即可。整套结构只有链段数上线性于操作次数，内存和时间都能通过。

复杂度

每个操作都只涉及常数次的有序集合查询与倍增跳跃，因此时间复杂度为 $O(\log n)$，空间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int q,n,k1,k2,k3,k4,k5,k6,k7,k8,k9,idx;
string s;
struct chn{
    int st;
    int ed;
    int dep;
    int chdep;
    int fa[23];
}P[400003];
set<pair<int,int> >R;
int getchn(int X){
    auto p=R.lower_bound(make_pair(X+1,-1000000));
    if(p==R.begin())return -1;
    p--;
    return (*p).second;
}
int getdep(int X){
    int uu=getchn(X);
    return P[uu].dep+(X-P[uu].st);
}
int chnLCA(int X,int Y){
    int c=20;
    if(P[X].chdep<P[Y].chdep)swap(X,Y);
    while(c--)if(P[P[X].fa[c]].chdep>=P[Y].chdep)X=P[X].fa[c];
    c=20;
    while(c--)if(P[X].fa[c]!=P[Y].fa[c])X=P[X].fa[c],Y=P[Y].fa[c];
    if(X==Y)return X;
    return P[X].fa[0];
}
int jumpDEP(int X,int chn,int tgt){
    if(chn==tgt)return P[chn].dep+(X-P[chn].st);
    for(int i=20;i>=0;i--)if(P[P[chn].fa[i]].dep>P[tgt].dep)chn=P[chn].fa[i];
    return P[chn].dep-1;
}
int KthPar(int X,int chn,int k){
    if(X-P[chn].st<k){k-=(X-P[chn].st);X=P[chn].st;}
    else return X-k;
    for(int i=20;i>=0;i--){
        if(!P[chn].fa[i])continue;
        if(P[chn].dep-P[P[chn].fa[i]].dep<=k){
            k-=P[chn].dep-P[P[chn].fa[i]].dep;
            chn=P[chn].fa[i];
        }
    }
    if(k==0)return P[chn].st;
    return P[P[chn].fa[0]].st+((P[chn].dep-k)-P[P[chn].fa[0]].dep);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>q;
    idx=n=1;
    P[n=1].st=P[n=1].ed=P[1].dep=P[1].chdep=1;
    R.insert(make_pair(1,1));
    while(q--){
        cin>>s;
        if(s[0]=='P'){
            cin>>k1>>k2;
            P[++n].st=idx+1;
            P[n].ed=idx+k2;
            idx+=k2;
            P[n].fa[0]=getchn(k1);
            P[n].dep=P[P[n].fa[0]].dep+(k1-P[P[n].fa[0]].st)+1;
            P[n].chdep=P[P[n].fa[0]].chdep+1;
            R.insert(make_pair(P[n].st,n));
            for(int i=1;i<=20;i++)P[n].fa[i]=P[P[n].fa[i-1]].fa[i-1];
        }
        else{
            cin>>k1>>k2;
            k3=getchn(k1);
            k4=getchn(k2);
            k5=chnLCA(k3,k4);
            k6=getdep(k1)+getdep(k2)-2*min(jumpDEP(k1,k3,k5),jumpDEP(k2,k4,k5));
            if(getdep(k1)>getdep(k2))cout<<KthPar(k1,k3,(k6/2))<<'\n';
            else cout<<KthPar(k2,k4,k6-(k6/2))<<'\n';
        }
    }
    return 0;
}