BruceJay's Blog

BZOJ2631 tree

| Comments

To start with

又刷了一道LCT裸题

Problem

Solution

支持四种操作:Link,Cut,链加,链乘。
Link和Cut直接LCT了,链加和链乘Splay打标记维护一下就好了。
感觉就是模板题。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned int ll;
const int N = 100100;
const int Mod = 51061;
int tr[N][2]; int fa[N];
bool rt[N]; int sz[N];
int st[N]; bool rev[N];
ll sum[N],val[N],a[N],b[N];
int n,m;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Calc(int u,int x,int y)
{
    sum[u]=(sum[u]*x+sz[u]*y)%Mod;
    val[u]=(val[u]*x+y)%Mod;
    a[u]=(a[u]*x)%Mod;
    b[u]=(b[u]*x+y)%Mod;
}

void Pushup(int x)
{
    int l=tr[x][0],r=tr[x][1];
    sz[x]=(sz[l]+sz[r]+1)%Mod;
    sum[x]=(sum[l]+sum[r]+val[x])%Mod;
}

void Pushdown(int x)
{
    int l=tr[x][0],r=tr[x][1];
    if(rev[x]){
        rev[x]^=1; rev[l]^=1; rev[r]^=1;
        swap(tr[x][0],tr[x][1]);
    }
    if(a[x]!=1 || b[x]!=0){
        if(l) Calc(l,a[x],b[x]);
        if(r) Calc(r,a[x],b[x]);
        a[x]=1; b[x]=0;
    }
}

void Rotate(int x)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(rt[y]) rt[y]=false,rt[x]=true;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Pushup(y); Pushup(x);
}

void Splay(int x)
{
    int top=0;
    for(int i=x;i;i=fa[i]) st[++top]=i;
    for(int i=top;i;i--) Pushdown(st[i]);
    while(!rt[x]){
        int y=fa[x];
        if(!rt[y]){
            int z=fa[y];
            if(tr[z][0]==y^tr[y][0]==x) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);      
    }
}

void Access(int x)
{
    int t=0;
    for(;x;x=fa[x]){
        Splay(x);
        rt[tr[x][1]]=true;
        tr[x][1]=t; rt[t]=false;
        Pushup(x); t=x;
    }
}

void Reverse(int x)
{
    Access(x); Splay(x); rev[x]^=1;
}

void Link(int u,int v)
{
    Reverse(v); Access(u); Splay(u);
    tr[u][1]=v; rt[v]=false; fa[v]=u;
    Pushup(u);
}

void Cut(int u,int v)
{
    Reverse(v); Access(u); Splay(u);
    rt[v]=true; tr[u][0]=fa[v]=0;
    Pushup(u);
}

int Query(int u,int v)
{
    Reverse(v); Access(u); Splay(u);
    return sum[u];
}

void Update(int u,int v,int x,int y)
{
    Reverse(v); Access(u); Splay(u);
    Calc(u,x,y);
}

int main()
{
    int u,v,x; char s[1];
    freopen("2631.in","r",stdin);
    freopen("2631.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++)
        val[i]=sz[i]=sum[i]=a[i]=1,rt[i]=true;
    for(int i=1;i<n;i++){
        u=read(); v=read();
        Link(u,v);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",s); u=read(); v=read();
        if(s[0]=='+'){
            x=read(); Update(u,v,1,x);
        }
        else if(s[0]=='-'){
            Cut(u,v);
            u=read(); v=read();
            Link(u,v);
        }
        else if(s[0]=='*'){
            x=read(); Update(u,v,x,0);
        }
        else printf("%d\n",Query(u,v));
    }
    return 0;
}

Last but not least

longlong是个大坑,更新标记过程中也应取模。

Comments

comments powered by Disqus