当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [usaco18Feb] New Barns

[usaco18Feb] New Barns

2019年03月14日  | 移动技术网IT编程  | 我要评论

WWW.WLZQ.COM.CN,789pao,小正太触手控

题意

每次新建一个节点，并与一个已知节点连边。（或者不连）。多次询问以某个已知点点出发的最远路径长度。

分析

显然，在任何时候图都是一个森林。由树的直径算法可知，与某点最远距的点必然是树的直径的一段。那么考虑在lct中维护直径。

实现

一篇精彩的lct,应该像少女穿的迷你裙,越短越好。——林语堂 （误

#include <bits/stdc++.h>
using namespace std;
const int n=1e5+10;

namespace lct {
    int ch[n][2],fa[n],siz[n]; bool rev[n];
    bool get(int x) {return ch[fa[x]][1]==x;}
    bool nrt(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
    void update(int x) {siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
    void pushdown(int x) {if(rev[x]) rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]),rev[x]=0;}
    void rotate(int x) {
        int y=fa[x],k=get(x); if(nrt(y)) ch[fa[y]][get(y)]=x;
        fa[x]=fa[y]; fa[ch[x][k^1]=fa[ch[y][k]=ch[x][k^1]]=y]=x; update(y);
    }
    void clear(int x) {if(nrt(x)) clear(fa[x]); pushdown(x);}
    void splay(int x) {
        for(clear(x); nrt(x); rotate(x)) 
            if(nrt(fa[x])) rotate(get(x)^get(fa[x])?x:fa[x]); 
        update(x);
    }
    void access(int x) {for(int y=0; x; update(y=x),x=fa[x]) splay(x),ch[x][1]=y;}
    void make(int x) {access(x); splay(x); rev[x]^=1;}
    void split(int x,int y) {make(x); access(y); splay(y);}
    void link(int x,int y) {split(x,y); fa[x]=y;}
    int length(int x,int y) {split(x,y); return siz[y]-1;}
}

int q,x,tot,l[n],r[n],bel[n];
char op[10];

int main() {
    scanf("%d",&q);
    while(q--) {
        scanf("%s%d",op,&x);
        if(*op=='q') {
            printf("%d\n",max(lct::length(x,l[bel[x]]),lct::length(x,r[bel[x]])));
            continue;
        }
        lct::siz[++tot]=1;
        if(x==-1) bel[tot]=tot,l[tot]=r[tot]=tot;
        else {
            lct::link(tot,x); bel[tot]=bel[x];
            int ll=lct::length(tot,l[bel[x]]);
            int lr=lct::length(tot,r[bel[x]]);
            int ld=lct::length(l[bel[x]],r[bel[x]]);
            if(ll>=lr&&ll>=ld) r[bel[x]]=tot;
            else if(lr>=ll&&lr>=ld) l[bel[x]]=tot;
        }
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网