洛谷1501 [国家集训队]Tree II

Luogu

分析

【模板】线段树2+【模板】Link-Cut Tree。

  • +:把$(u,v)$给$\texttt{split}$出来,再给$v$打标记。
  • *:和+差不多。
  • -:先$\texttt{cut}$,再$\texttt{link}$。
  • /:还是把$(u,v)$给$\texttt{split}$出来,再输出$v$的$sum$值。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

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

const int MOD=51061;
const int N=100000+10;

inline void add(int& x,int y) { x=(x+y)%MOD; }
inline void mul(int& x,int y) { x=1ll*x*y%MOD; }

struct Link_Cut_Tree {
    int ch[N][2],fa[N],sz[N],val[N];
    int sumv[N],addv[N],mulv[N],rev[N];
    int sta[N];
    inline void init(int n) { for (re int i=1;i<=n;++i) addv[i]=rev[i]=0,sumv[i]=val[i]=mulv[i]=1; }
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void reverse(int x) { if (!x) return; swap(ch[x][0],ch[x][1]),rev[x]^=1; }
    inline void plus(int x,int w) { add(sumv[x],w*sz[x]),add(val[x],w),add(addv[x],w); }
    inline void multi(int x,int w) { mul(sumv[x],w),mul(val[x],w),mul(addv[x],w),mul(mulv[x],w); }
    inline void pushup(int x) {
        sumv[x]=(sumv[ch[x][0]]+sumv[ch[x][1]]+val[x])%MOD;
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    }
    inline void pushdown(int x) {
        if (mulv[x]!=1) multi(ch[x][0],mulv[x]),multi(ch[x][1],mulv[x]),mulv[x]=1;
        if (addv[x]) plus(ch[x][0],addv[x]),plus(ch[x][1],addv[x]),addv[x]=0;
        if (rev[x]) reverse(ch[x][0]),reverse(ch[x][1]),rev[x]=0;
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?y:x);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x),splay(x),reverse(x); }
    inline void split(int x,int y) { makeroot(x),access(y),splay(y); }
    inline void link(int x,int y) { makeroot(x),fa[x]=y; }
    inline void cut(int x,int y) { split(x,y),fa[x]=ch[y][0]=0; }
} T;

int main() {
    int n=read(),q=read(); T.init(n);
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        T.link(u,v);
    }
    for (re int i=1;i<=q;++i) {
        char op[2]; scanf("%s",op);
        if (op[0]=='+') {
            int u=read(),v=read(),w=read();
            T.split(u,v),T.plus(v,w);
        }
        else if (op[0]=='*') {
            int u=read(),v=read(),w=read();
            T.split(u,v),T.multi(v,w);
        }
        else if (op[0]=='-') {
            int a=read(),b=read(),c=read(),d=read();
            T.cut(a,b),T.link(c,d);
        }
        else if (op[0]=='/') {
            int a=read(),b=read();
            T.split(a,b); printf("%d\n",T.sumv[b]);
        }
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 11 PM

发表评论