CF1137F Matches Are Not a Child's Play

╰+攻爆jí腚メ 2021-11-13 15:38 140阅读 0赞

[CF1137F Matches Are Not a Child's Play ][CF1137F_Matches Are Not a Child_s Play]

trick题目

考虑变成有根树，把最后删除的点当做根

就是n了

发现，up操作就是换根！

如果不换根？

直接求出序列查询即可

换根？

那么，新根y是最大值，原根x是次大值，

那么一定是把其他的点都直接删掉，最后剩下(x,y)路径的点，从x一路删到y

发现对于其他点删除的相对顺序不变

我们给(x,y)的路径打一个时间戳mx+1也就是当前最大权值+1

开始i的时间戳就是i的初始排名

那么一个点u的排名一定就是：

时间戳小于u的个数+u子树内时间戳和u一样的数

后者一定是一段连接u的链

并且我们发现，同一个时间戳一定连成的一个链，不会断开

这其实就是access！，再修改颜色

LCT进行换根，树状数组维护时间戳为x的数的个数

access换颜色的时候打标记，并且更新树状数组

**注意rotate是nrt(y)**

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    
    namespace Miracle{
    const int N=200000+5;
    int n,m;
    int lim;
    struct edge{
        int nxt,to;
    }e[2*N];
    int hd[N],cnt;
    priority_queue<int,vector<int>,greater<int> >q;
    void link(int x,int y){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        hd[x]=cnt;
    }
    int f[2*N];
    void add(int x,int c){
        for(;x<=lim;x+=x&(-x)) f[x]+=c;
    }
    int query(int x){
        int ret=0;
        for(;x;x-=x&(-x)) ret+=f[x];
        return ret;
    }
    struct node{
        int ch[2],fa;
        int rev,tim;
        int tag;
        int sz;
        void op(){
            cout<<" ch[0] "<<ch[0]<<" ch[1] "<<ch[1]<<" fa "<<fa<<endl;
        }
    }t[N];
    int du[N];
    void dfs(int x,int fa){
        t[x].sz=1;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa) continue;
            t[y].fa=x;
            dfs(y,x);
        }
    }
    #define ls t[x].ch[0]
    #define rs t[x].ch[1]
    bool nrt(int x){
        return (t[t[x].fa].ch[0]==x||t[t[x].fa].ch[1]==x);
    }
    void pushup(int x){
        if(x) t[x].sz=t[ls].sz+t[rs].sz+1;
    }
    void tag(int x,int c){
        t[x].tag=c;
        t[x].tim=c;
    }
    void rev(int x){
        t[x].rev^=1;
        swap(ls,rs);
    }
    void pushdown(int x){
        if(t[x].rev){
            rev(ls);rev(rs);
            t[x].rev=0;
        }
        if(t[x].tag){
            tag(ls,t[x].tag);tag(rs,t[x].tag);
            t[x].tag=0;
        }
    }
    void rotate(int x){
        int y=t[x].fa,d=t[y].ch[1]==x;
        t[t[y].ch[d]=t[x].ch[!d]].fa=y;
        if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;
        else t[x].fa=t[y].fa;
        t[t[x].ch[!d]=y].fa=x;
        pushup(y);
    }
    int sta[N];
    void splay(int x){
        int y=x,z=0;
        sta[++z]=y;
        while(nrt(y)) y=t[y].fa,sta[++z]=y;
        while(z) pushdown(sta[z--]);
    
        while(nrt(x)){
            y=t[x].fa,z=t[y].fa;
            if(nrt(y)){
                rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x);
            }
            rotate(x);
        }
        pushup(x);
    }
    void access(int x,int c){
        for(reg y=0;x;y=x,x=t[x].fa){
            splay(x);
            add(t[x].tim,-t[ls].sz-1);
            add(c,t[ls].sz+1);
            t[x].ch[1]=y;
            tag(x,c);
            pushup(x);
        }
    }
    void makert(int x,int c){
        access(x,c);splay(x);rev(x);
    }
    int rk(int x){
        splay(x);
        int ret=t[rs].sz+query(t[x].tim-1)+1;
        return ret;
    }
    int main(){
        rd(n);rd(m);
        lim=n+m;
        int x,y;
        int rt=n;
        for(reg i=1;i<n;++i){
            rd(x);rd(y);
            ++du[x];++du[y];
            link(x,y);link(y,x);
        }
        for(reg i=1;i<=n;++i) if(du[i]==1) q.push(i);
        int df=0;
        while(!q.empty()){
            int x=q.top();q.pop();
            t[x].tim=++df;
            add(df,1);
            for(reg i=hd[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(du[y]>1){
                    --du[y];
                    if(du[y]==1) q.push(y);
                }
            }
        }
        dfs(rt,0);
        char s[233];
        while(m--){
            scanf("%s",s+1);
            if(s[1]=='u'){
                ++df;
                rd(x);
                makert(x,df);
            }else if(s[1]=='w'){
                rd(x);printf("%d\n",rk(x));
            }else{
                rd(x);rd(y);
                int A=rk(x),B=rk(y);
                printf("%d\n",A<B?x:y);
            }
        }
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

考虑提出来根，然后就是换根

考虑换根对路径(x,y)的影响，发现时间戳很合适！

然后LCTaccess

转载于:https://www.cnblogs.com/Miracevin/p/10871586.html

[CF1137F_Matches Are Not a Child_s Play]: https://www.luogu.org/problemnew/show/CF1137F