课件链接

Problem A

考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。

由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $log$ 了，每次再用 $O(\sqrt{n+K})$ 来询问。

没有找到原题，代码咕咕咕QAQ……

K 小值查询

把集合分成三部分：$[1,k],(k,2k],(2k,+\infty)$ ，将第二部分提取出来暴力减去 $k$ 后重新加入集合，此时只剩下两部分 $[1,k],(2k,+\infty)$ ，后一部分减去 $k$ 后依然在第一部分后面，所以可以打tag。

因为第二部分至少除以 $2$ ，所以复杂度 $O(nlog_2nlog_2k)$ 。

操作均可以用Splay完成，好久没手写平衡树了……

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000,maxt=5e6;

int n,m;
int len,ro,son[maxt+5][2],val[maxt+5],num[maxt+5],si[maxt+5],tag[maxt+5];

#define cmp(p,k) ((k)==val[p]?-1:(k)>val[p])
inline void Pushup(int p) {si[p]=si[son[p][0]]+num[p]+si[son[p][1]];}
inline void Rotate(int &p,int d){
    int t=son[p][d];son[p][d]=son[t][d^1];son[t][d^1]=p;
    Pushup(p);Pushup(t);p=t;
}
inline void Addtag(int p,int k) {if (!p) return;val[p]+=k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;}
void Splay(int &p,int k){
    int d=cmp(p,k);if (d<0) return;Pushdown(p);int &s=son[p][d],f=cmp(s,k);
    if (~f) Splay(son[s][f],k),d==f?Rotate(p,d):Rotate(s,f);Rotate(p,d);
}
void Insert(int &p,int k,int x=1){
    if (!p) {p=++len;val[p]=k;num[p]=x;Pushup(p);return;}Pushdown(p);
    int d=cmp(p,k);if (~d) Insert(son[p][d],k,x); else num[p]+=x;Pushup(p);
}
int Askkth(int p,int k){
    Pushdown(p);int ls=si[son[p][0]];if (ls<k&&k<=ls+num[p]) return val[p];
    return k<=ls?Askkth(son[p][0],k):Askkth(son[p][1],k-ls-num[p]);
}
int Askpre(int p,int k){
    if (!p) return -1;Pushdown(p);int now=-1;if (val[p]<k) now=val[p];
    return k<=val[p]?max(now,Askpre(son[p][0],k)):max(now,Askpre(son[p][1],k));
}
int Asksuf(int p,int k){
    if (!p) return 2e9;Pushdown(p);int now=2e9;if (val[p]>k) now=val[p];
    return k>=val[p]?min(now,Asksuf(son[p][1],k)):min(now,Asksuf(son[p][0],k));
}
void Join(int p,int k){
    if (!p) return;Pushdown(p);Insert(ro,val[p]-k,num[p]);Splay(ro,val[p]-k);
    Join(son[p][0],k);Join(son[p][1],k);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1,x;i<=n;i++) scanf("%d",&x),Insert(ro,x),Splay(ro,x);
    for (int i=1;i<=m;i++){
        int tp,k,ans;scanf("%d%d",&tp,&k);
        if (tp==1) ans=Askkth(ro,k),Splay(ro,ans),printf("%d\n",ans); else{
            int L=Askpre(ro,k+1),R=Asksuf(ro,k<<1);
            if (L==-1&&R==2e9) Addtag(ro,-k);
            else if (L==-1) Splay(ro,R),Addtag(ro,-k);
            else if (R==2e9){
                Splay(ro,L);int now=son[ro][1];
                son[ro][1]=0;Pushup(ro);Join(now,k);
            } else{
                Splay(ro,L);Splay(son[ro][1],R);int now=son[son[ro][1]][0];
                son[son[ro][1]][0]=0;Addtag(son[ro][1],-k);
                Pushup(son[ro][1]);Pushup(ro);Join(now,k);
            }
        }
    }
    return 0;
}

抓 fafa 的 qzh

考虑离线，不难想到用cdq分治来处理，这样就把问题简化了很多。但是如果分治时间，就维护不了区间可爱值，分治可爱值，就保证不了时间顺序。

因此我们需要把一个询问 $[l,r]$ 拆成两个：$<l$ 的部分和 $<r+1$ 的部分，这样就不需要求区间可爱值。那么分治可爱值 $[l,r]$ ，然后用可爱值在 $[l,mid]$ 的修改操作贡献 $[mid+1,r]$ 的询问。

但是怎么维护一个点集能够查询 $x$ 到这个点集的距离和呢？和这道题差不多，只不过我们要维护的是链上加等差数列，可以用链剖+线段树或者LCT。

我讨厌数据结构……调了好久……

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=120000;

int n,m,Q;struct data {int tp,ID,x,y,z;} q[maxm+5],tem[2][maxm+5];LL ans[maxm+5];
int dep[maxn+5],son[maxn+5][2],fa[maxn+5],si[maxn+5];bool flip[maxn+5];
LL num[maxn+5],sum[maxn+5],tag[maxn+5][2],D[maxn+5],cnt,S;

#define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1])
#define Son(p) ((p)==son[fa[p]][1])
inline void Pushup(int p){
    si[p]=si[son[p][0]]+1+si[son[p][1]];
    sum[p]=sum[son[p][0]]+num[p]+sum[son[p][1]];
}
inline void Rotate(int t){
    int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addflip(int p) {
    if (!p) return;swap(son[p][0],son[p][1]);flip[p]^=1;
    tag[p][0]+=D[p]*(si[p]-1);D[p]=-D[p];
}
inline void Addtag(int p,int ID,LL k,LL d=0){
    if (!p) return;if (ID==1) num[p]+=k,sum[p]+=k*si[p],tag[p][1]+=k;
    if (!ID) num[p]+=k+d*si[son[p][0]],sum[p]+=(k+k+d*(si[p]-1))*si[p]/2,tag[p][0]+=k,D[p]+=d;
}
inline void Pushdown(int p){
    if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1;
    if (tag[p][0]||D[p]){
        LL k=tag[p][0],d=D[p];tag[p][0]=D[p]=0;
        Addtag(son[p][0],0,k,d);Addtag(son[p][1],0,k+d*(si[son[p][0]]+1),d);
    }
    if (tag[p][1]){
        LL k=tag[p][1];tag[p][1]=0;
        Addtag(son[p][0],1,k);Addtag(son[p][1],1,k);
    }
}
inline void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
inline int Access(int p,int x=0){
    for (int lst=0;p;x=lst=p,p=fa[p])
        Splay(p),son[p][1]=lst,Pushup(p);return x;
}
inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
inline void Link(int x,int y) {Makero(x);fa[x]=y;}
inline void Insert(int x,int y,int tp,int k,int d=0) {Makero(y);Access(x);Splay(x);Addtag(x,tp,k,d);}
inline int LCA(int x,int y) {return Makero(1),Access(x),Access(y);}
inline int Size(int x,int y) {Makero(y);Access(x);Splay(x);return si[x];}
inline LL Ask(int x) {Makero(1);Access(x);Splay(x);return sum[x];}
inline void Update(int x,int y,int f){
    int lca=LCA(x,y),si=Size(x,y);Insert(lca,x,0,f,f);Insert(lca,y,0,f,f);
    Insert(lca,1,1,f*si);Splay(lca);num[lca]-=f*(si+1);Pushup(lca);
    cnt+=f*(dep[x]-dep[lca]+dep[y]-dep[lca]+1);S-=f*dep[lca];
    S+=f*((LL)(dep[x]+dep[lca])*(dep[x]-dep[lca]+1)>>1);
    S+=f*((LL)(dep[y]+dep[lca])*(dep[y]-dep[lca]+1)>>1);
}
void Solve(int L,int R,int l=-1e9,int r=1e9+1){
    if (L==R||l==r) return;int mid=l+(r-l>>1),A=0,B=0;
    for (int i=L;i<=R;i++){
        int tp=q[i].tp,ID=q[i].ID,x=q[i].x,y=q[i].y,z=q[i].z;
        if (z<=mid) tem[0][A++]=q[i]; else tem[1][B++]=q[i];
        if (tp==1&&z<=mid) Update(x,y,1);if (tp==2&&z>mid) ans[ID]+=y*(S+(LL)dep[x]*cnt-(Ask(x)<<1));
    }for (int i=L;i<=R;i++) if (q[i].tp==1&&q[i].z<=mid) Update(q[i].x,q[i].y,-1);
    for (int i=0;i<A;i++) q[L+i]=tem[0][i];for (int i=0;i<B;i++) q[L+A+i]=tem[1][i];
    if (A) Solve(L,L+A-1,l,mid);if (B) Solve(L+A,R,mid+1,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) si[i]=1;
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Link(x,y);
    for (int i=1;i<=n;i++) dep[i]=Size(1,i);
    for (int i=1;i<=m;i++){
        int tp,x,y,z;scanf("%d%d%d%d",&tp,&x,&y,&z);
        if (tp==1) q[++Q]=(data){tp,i,x,y,z},ans[i]=-1;
        else q[++Q]=(data){tp,i,z,-1,x},q[++Q]=(data){tp,i,z,1,y+1};
    }Solve(1,Q);for (int i=1;i<=m;i++) if (~ans[i]) printf("%lld\n",ans[i]);return 0;
}

Product on the segment

AwD说的那个好神仙啊……我只会 $O(nlog_2n+q)$ 啊……

区间修改我们会想到ST表，但是ST表有重叠部分就GG了。我们需要用到一个和ST表有些类似的数据结构，定义 $A_{i,j}=\prod_{k=\lfloor{i\over 2^j}\rfloor2^j}^{i}a_k,B_{i,j}=\sum_{k=i}^{\lceil{i\over 2^j}\rceil2^j-1}a_k$ ，这可以直接 $O(nlog_2n)$ 处理。

然后询问区间 $[L,R]$ ，如果 $L=R$ 那么就是 $a_L$ ，否则我们需要找到一个 $k$ 使得 $[L,R]$ 内只存在一个 $2^k$ 的倍数，这样的话就可以直接 $B_{L,k}A_{R,k}$ 得出结果。

怎么找呢？上结论！$highbit(L\ xor\ R)$ 就是一个合法的 $k$ ，这很显然。

然后还需要卡卡常才能过。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000000,maxm=312502,Log=20,maxs=1<<Log;

int T,n,MOD,te,ans,a[maxn+5],b[maxm+5],A[Log+5][maxn+5],B[Log+5][maxn+5],Lg[maxs];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define L(i,k) ((i)>>(k)<<(k))
#define R(i,k) (((i)+(1<<(k))>>(k)<<(k))-1)
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int main(){
    freopen("SEGPROD.in","r",stdin);freopen("SEGPROD.out","w",stdout);
    for (int j=1;j<Log;j++) Lg[1<<j]=j;for (int i=1;i<maxs;i++) if (!Lg[i]) Lg[i]=Lg[i-1];
    for (readi(T);T;T--){
        readi(n);readi(MOD);readi(te);
        for (int i=0;i<n;i++) readi(a[i]),A[0][i]=B[0][i]=a[i];
        for (int i=0;i<(te>>6)+2;i++) readi(b[i]);
        for (int j=1;(1<<j)<=n;j++){
            A[j][0]=1;for (int i=0;i<=n-1;i++) A[j][i]=(L(i,j)==i?a[i]:MUL(A[j][i-1],a[i]));
            B[j][n]=1;for (int i=n-1;i>=0;i--) B[j][i]=(R(i,j)==i?a[i]:MUL(B[j][i+1],a[i]));
        }
        for (int i=ans=0,L=0,R=0;i<te;i++){
            if (!(i&63)) L=b[i>>6],R=b[(i>>6)+1];L=(L+ans)%n;R=(R+ans)%n;
            if (L>R) swap(L,R);int k=Lg[L^R];ans=ADD((L==R?a[L]:(LL)B[k][L]*A[k][R]),1);
        }printf("%d\n",ans);
    }return 0;
}

Reverse Game

怎么网上的题解都说的轻描淡写啊……我感觉这道题的实现技巧还是很巧妙的……

由于只有单点操作和列操作，所以我们可以对列建线段树，在线段树上维护连通块个数。

怎么维护啊？并查集大法好。每个节点 $[l,r]$ 维护开头( $l$ )列的信息以及结尾( $r$ )列的信息，通过合并左儿子的结尾以及右儿子的开头信息来维护连通块个数。但是很明显我们不能对每列开并查集，而是要用一个全局并查集来维护连通信息。

这就出现了一个问题，每次修改之后全局并查集信息都会发生大面积变化，为了方便维护，我们在刚开始维护每列信息的时候，不使用全局并查集，而是直接通过记录编号的方法来标记连通块，这样就可以保证每次修改之前并查集 $father_x=x$ ，因此我们可以直接记录下所有变化过的位置，在每次询问完成之后将这些值初始化。

#include<cstdio>
#include<vector>
#define pb push_back
using namespace std;
const int maxn=200,maxm=maxn*maxn;

int T,n,te,fat[maxm+5];bool a[maxn+5][maxn+5],vis[maxm+5];vector<int> v;
int fa[(maxn<<2)+5][2][maxn+5],num[(maxn<<2)+5][2];

#define ID(x,y) (((x)-1)*n+y)
inline void Addtag(int x) {if (!vis[x]) v.pb(x),vis[x]=true;}
int getfa(int x) {return x==fat[x]?x:(Addtag(x),fat[x]=getfa(fat[x]));}
inline void Makefa(int p,int j){
    num[p][a[1][j]]=1;num[p][a[1][j]^1]=0;fa[p][0][1]=fa[p][1][1]=ID(1,j);
    for (int i=2,lst=1;i<=n;i++){
        if (a[i][j]!=a[i-1][j]) lst=i,num[p][a[i][j]]++;
        fa[p][0][i]=fa[p][1][i]=ID(lst,j);
    }
}
inline void Pushup(int p,int l,int r){
    for (int f=0;f<2;f++) num[p][f]=num[p<<1][f]+num[p<<1|1][f];
    for (int i=1;i<=n;i++)
        if (a[i][l]==a[i][r]){
            int x=getfa(fa[p<<1][1][i]),y=getfa(fa[p<<1|1][0][i]);if (x==y) continue;
            Addtag(x);fat[x]=y;num[p][a[i][l]]--;
        }
    for (int i=1;i<=n;i++) fa[p][0][i]=getfa(fa[p<<1][0][i]),fa[p][1][i]=getfa(fa[p<<1|1][1][i]);
}
void Build(int L,int R,int p=1){
    if (L==R) return Makefa(p,L);int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p,mid,mid+1);
}
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) return Makefa(p,pos);int mid=l+(r-l>>1);
    pos<=mid?Update(pos,l,mid,p<<1):Update(pos,mid+1,r,p<<1|1);Pushup(p,mid,mid+1);
}
inline void Clear() {for (int i=0,si=v.size();i<si;i++) fat[v[i]]=v[i],vis[v[i]]=false;v.clear();}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&T);T;T--){
        scanf("%d",&n);for (int i=1;i<=n;i++) for (int j=1,x;j<=n;j++) scanf("%d",&x),a[i][j]=x;
        for (int i=1;i<=n*n;i++) fat[i]=i;Build(1,n);Clear();
        for (scanf("%d",&te);te;te--){
            int tp,x,y;scanf("%d%d",&tp,&x);
            if (tp==2) scanf("%d",&y),a[x][y]^=1,Update(y);
            else {for (int i=1;i<=n;i++) a[i][x]^=1;Update(x);}
            for (int i=1;i<=n;i++)
                if (a[i][1]==a[i][n]){
                    int x=getfa(fa[1][0][i]),y=getfa(fa[1][1][i]);if (x==y) continue;
                    Addtag(x);fat[x]=y;num[1][a[i][1]]--;
                }
            printf("%d %d\n",num[1][0],num[1][1]);Clear();
        }
    }
    return 0;
}

Problem B

直接贪心，答案肯定是从最早的黑点 $x$ 开始走，每次找到第一个 $>x+L$ 的黑点跳过去。那么所有黑点构成了一棵树，用LCT维护这棵树就可以快速求答案。

但是修改的时候会引发大量信息改动啊？大概和这题差不多，通过建虚点来快速修改就行了：在每个位置建一个灰点，黑点连向 $x+L$ 的灰点，灰点连向最近的黑点或灰点，这样连向每个黑点的就只有一个灰点，修改的点数就是 $O(1)$ 的了。

没有找到原题，代码咕咕咕QAQ……

Maximum Tree Path

题解戳这里

⼤ sz 的游戏

线段树标记永久化的方法我并没有看……反正可以KDT暴搞……题解戳这里

Count on a Treap

要利用好Treap的性质，Treap的建立过程可以看作是先按照键值排序，然后选出权值最大的点当做根，之后左右两边递归。

也就是说两个点的 $x,y$ 的 $LCA$ 是他们在DFS序中权值最大的点，因此算距离就可以用 $deep_x+deep_y-2deep_{LCA}$ 。

根据上面那个结论，$x$ 点的父亲就是离自己最近的权值大于 $w_x$ 的点，我们只需要不停地找父亲就可以得到深度，会发现这就是求两端上升序列长度。

因此离线之后用线段树维护一下就行了。

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<unordered_map>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef unsigned int uint;
const int maxm=200000,maxn=maxm;

int n,m,tp[maxm+5];uint a[maxm+5],b[maxm+5],val[maxn+5],w[maxn+5];unordered_map<uint,int> f;
int l[(maxn<<2)+5],r[(maxn<<2)+5],lw[(maxn<<2)+5],rw[(maxn<<2)+5],MAX[(maxn<<2)+5];uint lst;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
int FindL(int p,uint k){
    if (l[p]==r[p]) return w[MAX[p]]>k;
    else if (k>=w[MAX[p<<1|1]]) return FindL(p<<1,k);
    else return FindL(p<<1|1,k)+lw[p];
}
int FindR(int p,uint k){
    if (l[p]==r[p]) return w[MAX[p]]>k;
    else if (k>=w[MAX[p<<1]]) return FindR(p<<1|1,k);
    else return FindR(p<<1,k)+rw[p];
}
inline int Maxer(int x,int y) {return w[x]>w[y]?x:y;}
inline void Pushup(int p){
    MAX[p]=Maxer(MAX[p<<1],MAX[p<<1|1]);
    lw[p]=FindL(p<<1,w[MAX[p<<1|1]]);
    rw[p]=FindR(p<<1|1,w[MAX[p<<1]]);
}
void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;if (L==R) {MAX[p]=L;return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
void Update(int pos,int p=1){
    if (l[p]==r[p]) return;int mid=l[p]+(r[p]-l[p]>>1);
    pos<=mid?Update(pos,p<<1):Update(pos,p<<1|1);Pushup(p);
}
int Askmax(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R) return MAX[p];int mid=l[p]+(r[p]-l[p]>>1);
    if (R<=mid) return Askmax(L,R,p<<1); else if (L>mid) return Askmax(L,R,p<<1|1);
    else return Maxer(Askmax(L,mid,p<<1),Askmax(mid+1,R,p<<1|1));
}
int AskL(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R) {int now=FindL(p,lst);lst=max(lst,w[MAX[p]]);return now;}
    int mid=l[p]+(r[p]-l[p]>>1);
    if (R<=mid) return AskL(L,R,p<<1); else if (L>mid) return AskL(L,R,p<<1|1);
    else return AskL(mid+1,R,p<<1|1)+AskL(L,mid,p<<1);
}
int AskR(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R) {int now=FindR(p,lst);lst=max(lst,w[MAX[p]]);return now;}
    int mid=l[p]+(r[p]-l[p]>>1);
    if (R<=mid) return AskR(L,R,p<<1); else if (L>mid) return AskR(L,R,p<<1|1);
    else return AskR(L,mid,p<<1)+AskR(mid+1,R,p<<1|1);
}
inline int Deep(int x){
    int ans=1;lst=w[x];ans+=(x>1?AskL(1,x-1):0);
    lst=w[x];ans+=(x<n?AskR(x+1,n):0);return ans;
}
int main(){
    freopen("COT5.in","r",stdin);freopen("COT5.out","w",stdout);
    readi(m);for (int i=1;i<=m;i++){
        readi(tp[i]);readi(a[i]);if (tp[i]!=1) readi(b[i]);
        if (!tp[i]) val[++n]=a[i];
    }sort(val+1,val+1+n);for (int i=1;i<=n;i++) f[val[i]]=i;Build(1,n);
    for (int i=1,pos;i<=m;i++)
        if (!tp[i]) pos=f[a[i]],w[pos]=b[i],Update(pos);
        else if (tp[i]==1) pos=f[a[i]],w[pos]=0,Update(pos); else{
            int x=f[a[i]],y=f[b[i]],lca;if (x>y) swap(x,y);lca=Askmax(x,y);
            printf("%d\n",Deep(x)+Deep(y)-(Deep(lca)<<1));
        }
    return 0;
}