LOJ2474

Description

对于一颗树 ，定义无向简单图 中上的两点 之间有边当且仅当 中 之间的路径上的所有点编号都小于 。

有一棵树 ，初始时只有一个点，编号为 ，接下来有 次操作，操作有以下两种：

• 表示加入一个编号为 的节点并与当前编号为 的节点相连（保证任何时刻不会有两个编号相同的节点）；
• 表示查询 中点 到 的最短路（每条边长度均为 ）。

请你回答所有查询。

Input

第一行两个整数 ，表示编号的最大可能值及询问个数。

接下来 行每行三个整数 ，以题目描述中的格式描述一次操作。

Output

依次对于每一个 类型的操作，输出一行一个整数表示其对应的答案。

Sample Input

7 10
1 1 2
1 2 3
1 3 5
1 5 6
2 1 6
1 1 4
2 1 6
1 1 7
2 1 6
2 3 6

Sample Output

4
3
2
2

Solution

假定读者已经大致看过论文和 zx2003 的博客了

重点就是两个函数：qry(x,y) 和 add(x,y)

qry(x,y)

只需要分别找 到 LCA（或其祖先） 的最小步数和最后一步之前（即跳”最小步数 “步）的位置，再判断 能否一步到 即可

即实现一个 query(x,z) 函数返回 pair(step,point)

先求跳的步数，发现就是 C 中 到 或其祖先的路径上（不包括最后的 或其祖先）点权之和 ； 特殊的，如果在跳到 （及其祖先）之前最上面的点权为 ，则不用 ，相当于已经算过跳上去这一步的贡献

query.png

再求跳了最小步数 能跳到哪里，不难发现是跳到 （及其祖先）之前最上面的那一个 "1" 的前驱（如果 "1" 恰好是 （及其祖先）之前最上面的一个则忽略这个 "1" ，用第二个 "1" 来找前驱）

求 能否一步到 即判断在 C 上 是否能到达 ，即 向其含有 的子树内连的一条链的链底是否是 的子孙。

易得 连的链底就是 到 路径上离 最近的点，然后就可以 check 了

add(x,y)

先判掉 的情况，这时直接 C 中连一下且 F 中

否则 ， 会插入成 的祖先。C 中 会向 及其祖先连边直到 本身

到 在 C 中形成的链的一部分后缀的点的 F 中的 fa 会改为

需要把这条链上的点权都变成

同时可能会影响某些点权为 的点，需要把它们点权变为 并把他们 LCT 上的父亲改为指向它们的 F （具体见最后一部分）

特别注意这里的 access 每次不是跳 F 中的 fa 而是 C 中的 fa ！！！

（因为 C 中的 fa 不一定是 F 中的 fa，当点权为 时相当于跳了一大段 C 中的祖先）

然后把跳到 的链上的点的点权全变成 ，链顶点权设为 并接在 上

至于 在 C 及 F 上的父亲，可以发现和之前在 位置上的点（ 祖先中最大的编号小于 的点）相同。

关于 0 变 1 的处理

• 一种是从定义上，可以发现是 到其在 C 中的父亲所夹的连通块中的最大值，可以通过求连通块任意一点一直跳 fa 直到 之前的最后一点得到

• 一种是考虑特殊处理 LCT 上的链，若能保证每个链头点权都为 那么直接找 u 在 LCT 上的后继即可；（但这种 access 要多写一堆东西防止断边出现链头 ……）

  • add 函数中特殊情况新建的链头以及 access 时断开的链的链头都会变 1；
  • query 函数中 access 提取一条链时可能会断开一个链使得 作为链头，这时可以直接强行将其点权变为 ，即强行让其指向它 F 中的父亲

Code

#include<bits/stdc++.h>
#define FIO "L2474"
#define ll long long
#define pii std::pair<int,int>
//#define DEBUG

const int N=1e5+5,Q=5e5+5,lgN=18;

using namespace std;
int premax,vis[N];

int n,q,op[Q],u[Q],v[Q];

struct Graph{
  int h[N],to[N<<1],nxt[N<<1],ecnt;
  int fa[N];
  int dfn[N],sz[N],cnt;
  inline void adde(int u,int v){nxt[++ecnt]=h[u];h[u]=ecnt;to[ecnt]=v;}
  inline void add(int u,int v){adde(u,v);adde(v,u);}
}T,C;

struct DSU{
  int f[N];
  inline void init(){
    for(int i=1;i<=n;i++)f[i]=i;
  }
  inline int find(int x){
    while(x^f[x])x=f[x]=f[f[x]];
    return x;
  }
  inline void merge(int x,int y){
    if((x=find(x))==(y=find(y)))return;
    C.add(x,y);
    f[x]=y;
  }
}U;

int mx[N<<1][lgN],lg[N<<1];
int dcnt,id[N];
set<int>s[N];
int top[N],mxs[N],cfa[N];

inline void dfsC(int u,int fa=0){
  C.dfn[u]=++C.cnt;
  C.sz[u]=1;
  mx[id[u]=++dcnt][0]=u;

  for(int i=C.h[u],v;i;i=C.nxt[i])if((v=C.to[i])^fa){
    cfa[v]=u;
    dfsC(v,u);
    if(C.sz[v]>C.sz[mxs[u]])mxs[u]=v;
    C.sz[u]+=C.sz[v];
    mx[++dcnt][0]=u;
  }
}

inline void dfs2(int u,int tp){
  top[u]=tp;
  if(mxs[u])dfs2(mxs[u],tp);
  for(int i=C.h[u],v;i;i=C.nxt[i])if((v=C.to[i])^cfa[u]&&v^mxs[u])
    dfs2(v,v);
}

std::vector<int>son[N];

inline int cmp(const int &x,const int &y){
  return T.dfn[x]<T.dfn[y];
}

inline void dfsT(int u,int fa=0){
  T.dfn[u]=++T.cnt;
  T.sz[u]=1;

  for(int i=T.h[u],v;i;i=T.nxt[i])if((v=T.to[i])^fa){
    T.fa[v]=u;
    dfsT(v,u);
    T.sz[u]+=T.sz[v];
    son[u].push_back(v);
  }
}

inline int lca(int x,int y){
  x=id[x];y=id[y];
  if(x>y)std::swap(x,y);
  int t=lg[y-x+1];
  return std::max(mx[x][t],mx[y-(1<<t)+1][t]);
}

inline void init(){
  U.init();
  for(int u=1;u<=n;u++){
    for(int i=T.h[u],v;i;i=T.nxt[i])if((v=T.to[i])<u){
      U.merge(v,u);
    }
  }
  for(int i=n;i;i--)if(!id[i])dfsC(i);
  for(int i=n;i;i--)if(!top[i])dfs2(i,i);
  for(int i=1;i<=n;i++)if(!T.dfn[i])dfsT(i);

  lg[0]=-1;
  for(int i=1;i<=dcnt;i++)lg[i]=lg[i>>1]+1;
  for(int j=1;(1<<j)<=dcnt;j++)
    for(int i=1;i+(1<<j)-1<=dcnt;i++)
      mx[i][j]=std::max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}

int ch[N][2],fa[N];
int w[N],sum[N];

#define lx ch[x][0]
#define rx ch[x][1]
#define chk(x) ((x)==ch[fa[x]][1])
#define isrt(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)

inline void pushup(int x){
  sum[x]=sum[lx]+w[x]+sum[rx];
}

inline void rotate(int x){
  int y=fa[x],z=fa[y],t=chk(x);
  fa[ch[x][!t]]=y;
  ch[y][t]=ch[x][!t];
  fa[x]=z;
  if(!isrt(y))ch[z][chk(y)]=x;
  ch[x][!t]=y;
  fa[y]=x;
  pushup(y);
  pushup(x);
}

/*
inline void out_lct(){
  for(int i=1;i<=n;i++)if(vis[i]){
    printf("%d:fa=%d ch=(%d,%d) w=%d s=%d\n",i,fa[i],ch[i][0],ch[i][1],w[i],sum[i]);
  }
  puts("");
}

vector<int>STA;
int tim,lst[N];

inline void dfs(int x,int tim){
  if(!x)return;
  lst[x]=tim;
  dfs(lx,tim);
  STA.push_back(x);
  dfs(rx,tim);
}

inline void checkGG(){
  for(int i=1;i<=n;i++)if((ch[i][0]&&i>ch[i][0])||i<ch[i][1]){
    printf("GG in %d\n",i);
    cout.flush();
    assert(i<=ch[i][0]&&i>=ch[i][1]);
  }
}

inline void out_C(){
  for(int i=1;i<=n;i++)if(vis[i]){
    printf("%d:C.fa=%d\n",i,C.fa[i]);
  }
}
*/

inline void splay(int x){
  assert(x);
  for(int y=fa[x];!isrt(x);rotate(x),y=fa[x])if(!isrt(y))
    rotate(chk(x)^chk(y)?x:y);
}

/*
inline void checkorder(){
  tim++;
  for(int i=1;i<=n;i++)if(lst[i]!=tim){
    STA.clear();
    splay(i);
    dfs(i,tim);
    for(int i=1,sz=STA.size();i<sz;i++){
      if(STA[i]>STA[i-1]){
        out_lct();
        printf("STA=");
        for(int i=0;i<sz;i++)
          printf("%d ",STA[i]);
        puts("");
      }
      cout.flush();
      assert(STA[i]<=STA[i-1]);
    }
  }
}

*/

inline int find_fir(int x){
  while(lx)x=lx;
  return x;
}

inline int find_one(int x,int prefer){
  if(!sum[x])assert(0);
  while(x){
    if(sum[ch[x][prefer]])x=ch[x][prefer];
    else if(w[x])return x;
    else x=ch[x][!prefer];
  }
  assert(0);
}

inline int find_pre(int x){
  splay(x);
  if(!lx)return fa[x];
  x=lx;
  while(rx)x=rx;
  return x;
}

inline void link(int x,int y,int flag=1){
  if(y)assert(x<y);
  splay(x);
  if(y)splay(y);

  w[x]=1;
  pushup(x);

  if(flag&&y){

    if(ch[y][1]){
      int tmp=find_fir(ch[y][1]);

      fa[ch[y][1]]=0;
      splay(tmp);
      ch[y][1]=0;
      if(!w[tmp]){

        link(tmp,find_pre(find_one(y,1)),0);

      }
    }

    ch[y][1]=x;
    pushup(y);
  }

  fa[x]=y;

}

inline int upper_floor(int x,int z){
  int ret=x;
  while(x){
    if(x<z){
      ret=x;
      x=lx;
    }else x=rx;
  }
  return ret;
}

inline pii query(int x,int z){
  if(x==z)return pii(0,x);
  pii ret;
  ret.second=x;

  int y=0;
  while(x){
    splay(x);

    if(rx){

      int w=rx;
      rx=0;
      w=find_fir(w);

      pushup(x);
      if(!::w[w]){
        splay(w);
        fa[w]=0;
        int tt=find_pre(find_one(x,1));
        link(w,tt,0);
      }

      splay(x);
    }
    rx=y;
    pushup(x);

    if(!(fa[x]&&fa[x]<z))break;
    y=x;
    x=fa[x];
  }

  //printf("x=%d lower=%d\n",x,upper_floor(x,z));
  splay(x);

  x=upper_floor(x,z);
  splay(x);
  ret.first=sum[rx]+1;
  if(sum[rx])
    ret.second=find_pre(find_one(rx,0));
  return ret;
}

inline bool in(int *dfn,int *sz,int x,int y){
  return dfn[y]<=dfn[x]&&dfn[x]<dfn[y]+sz[y];
}

inline int get_down(int x,int y){
  if(!in(T.dfn,T.sz,y,x))return T.fa[x];
  assert(x^y);
  int z=*--upper_bound(son[x].begin(),son[x].end(),y,cmp);
  return z;
}

inline bool check(int x,int y){
  if(x==y)return 1;
  cout.flush();
  int z=get_down(y,x);
  return in(C.dfn,C.sz,z,x);
}

inline int qry(int x,int y){
  //printf("------------\nqry %d %d\n",x,y);
  int z=lca(x,y);
  pii a=query(x,z),b=query(y,z);


#ifdef DEBUG
  printf("a=(%d,%d)\n",a.first,a.second);
  printf("b=(%d,%d)\n",b.first,b.second);
  printf("lca=%d\n",z);
#endif

  return a.first+b.first+!(check(a.second,z)&&check(b.second,z));
}


inline int access(int x){
  int y=0;
  while(x){
    splay(x);

    if(rx){
      int w=rx;
      rx=0;
      pushup(x);
      w=find_fir(w);
      if(!::w[w]){
        splay(w);
        fa[w]=0;
        int tt=find_pre(find_one(x,1));
        link(w,tt,0);
      }
      splay(x);
    }
    rx=y;
    pushup(x);

    if(!fa[x]||sum[x])break;

    y=x;
    x=fa[x];
  }

  if(sum[x])
    return find_one(x,1);
  else return find_fir(x);
}

inline int getson(int x,int y){
  int ret=x;
  assert(x);

  while(top[x]^top[y]){
    if(s[top[x]].size())
      ret=*s[top[x]].rbegin();
    x=cfa[top[x]];
  }
  set<int>::iterator it=s[top[x]].lower_bound(y);
  if(it!=s[top[x]].begin()){
    ret=*--it;
  }

  /*
  while(C.fa[x]&&C.fa[x]<y){
    x=C.fa[x];
    if(vis[x])ret=x;
  }
  */

  return ret;
}

inline void add(int x,int y){
  if(x>y){
    link(y,x,0);
    C.fa[y]=x;
    s[top[y]].insert(y);
    return;
  }

  int z=getson(x,y);
  s[top[y]].insert(y);

  std::vector<int>v;
  int lstx=0;

  while(x){
    v.push_back(x);
    x=access(x);
    int z=find_pre(x);
    if(z>y){
      v.pop_back();
      break;
    }
    splay(x);

    lstx=x;
    fa[lx]=fa[x];
    w[x]=fa[x]=lx=0;
    pushup(x);
    x=C.fa[x];
  }

#ifdef DEBUG
  printf("v={"); for(int i=0,szv=v.size();i<szv;i++)printf("%d,",v[i]); puts("}");
#endif

  for(int i=0,szv=v.size();i<szv-1;i++){
    splay(v[i]);
    splay(v[i+1]);
    assert(!ch[v[i+1]][1]);
    ch[v[i+1]][1]=v[i];
    fa[v[i]]=v[i+1];
    pushup(v[i+1]);
  }


  if(v.size())
    link(lstx,y,0);
  /*
   * !!!
     the same as
  {
    splay(v.back());
    link(find_fir(v.back()),y,0);
  }
  */

  C.fa[y]=C.fa[z];
  C.fa[z]=y;

  if(!C.fa[y]){
    return;
  }

  splay(z);

  //printf("Before add y to tree:(son=%d)\n",x); out_lct();

  ch[y][0]=ch[z][0];
  if(ch[z][0])fa[ch[z][0]]=y;
  ch[z][0]=y;
  fa[y]=z;
  w[y]=w[z];
  w[z]=0;
  pushup(y);
  pushup(z);

}

int main(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=q;i++){
    scanf("%d%d%d",&op[i],&u[i],&v[i]);
    if(op[i]==1){
      T.add(u[i],v[i]);
    }
  }

  vis[1]=1;

  init();

  for(int i=1;i<=q;i++){
    if(op[i]==1){
      premax=max(premax,v[i]);
      vis[v[i]]=1;
      add(u[i],v[i]);
    }else
    printf("%d\n",qry(u[i],v[i]));
#ifdef DEBUG
  //out_lct(); out_C(); puts("===========");
#endif
  }

  return 0;
}