洛谷 P1501 [国家集训队]Tree II 解题报告

P1501 [国家集训队]Tree II

题目描述

一棵\(n\)个点的树，每个点的初始权值为\(1\)。对于这棵树有\(q\)个操作，每个操作为以下四种操作之一：

• + u v c：将\(u\)到\(v\)的路径上的点的权值都加上自然数\(c\)；
• - u1 v1 u2 v2：将树中原有的边\((u_1,v_1)\)删除，加入一条新边\((u_2,v_2)\)，保证操作完之后仍然是一棵树；
• * u v c：将\(u\)到\(v\)的路径上的点的权值都乘上自然数\(c\)；
• / u v：询问\(u\)到\(v\)的路径上的点的权值和，求出答案对于\(51061\)的余数。

输入输出格式

输入格式：

第一行两个整数\(n,q\)

接下来\(n-1\)行每行两个正整数\(u,v\)，描述这棵树

接下来\(q\)行，每行描述一个操作

输出格式：

对于每个/对应的答案输出一行

说明

\(10\%\)的数据保证，\(1<=n\)，\(q<=2000\)

另外\(15\%\)的数据保证，\(1<=n\)，\(q<=5*10^4\)，没有-操作，并且初始树为一条链

另外\(35\%\)的数据保证，\(1<=n\)，\(q<=5*10^4\)，没有-操作

\(100\%\)的数据保证，\(1<=n,q<=10^5\)，\(0<=c<=10^4\)

---

就是个LCTsb题

然后我放乘法标记的时候忘记放到加法标记上了，记录一下自己的sb错误。

注意要开uint

---

Code:

#include <cstdio>

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

const unsigned int mod=51061;

const unsigned int N=1e5+10;

unsigned int ch[N][2],par[N],sum[N],dat[N],tag[N],add[N],mul[N],siz[N],s[N],tot,tmp,n,m;

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

unsigned int identity(int now){return ch[fa][1]==now;}

void connect(int f,int now,int typ){ch[f][typ]=now,fa=f;}

void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;}

void updata(int now){sum[now]=(sum[ls]+sum[rs]+dat[now])%mod;siz[now]=siz[ls]+siz[rs]+1;}

void pushdown(int now)

{

    if(tag[now]){if(ls) Reverse(ls);if(rs) Reverse(rs);tag[now]^=1;}

    if(ls)

    {

        sum[ls]=(sum[ls]*mul[now]+add[now]*siz[ls])%mod;

        dat[ls]=(dat[ls]*mul[now]+add[now])%mod;

        mul[ls]=mul[ls]*mul[now]%mod;

        add[ls]=(add[ls]*mul[now]+add[now])%mod;

    }

    if(rs)

    {

        sum[rs]=(sum[rs]*mul[now]+add[now]*siz[rs])%mod;

        dat[rs]=(dat[rs]*mul[now]+add[now])%mod;

        mul[rs]=mul[rs]*mul[now]%mod;

        add[rs]=(add[rs]*mul[now]+add[now])%mod;

    }

    add[now]=0,mul[now]=1;

}

void Rotate(int now)

{

    int p=fa,typ=identity(now);

    connect(p,ch[now][typ^1],typ);

    if(isroot(p)) connect(par[p],now,identity(p));

    else fa=par[p];

    connect(now,p,typ^1);

    updata(p),updata(now);

}

void splay(int now)

{

    while(isroot(now)) s[++tot]=now,now=fa;

    s[++tot]=now;

    while(tot) pushdown(s[tot--]);

    now=s[1];

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

void access(int now)

{

    for(int las=0;now;las=now,now=fa)

        splay(now),rs=las,updata(now);

}

void evert(int now){access(now),splay(now),Reverse(now);}

void link(int u,int v){evert(u),par[u]=v;}

void makeline(int u,int v){evert(u),access(v),splay(v);}

void cat(int u,int v){makeline(u,v),ch[v][0]=par[u]=0,updata(v);}

unsigned int query(int u,int v){makeline(u,v);return sum[v];}

void Add(int u,int v,unsigned int d)

{

    makeline(u,v);

    (dat[v]+=d)%=mod,(sum[v]+=d*siz[v])%=mod,(add[v]+=d)%=mod;

}

void Mul(int u,int v,unsigned int d)

{

    makeline(u,v);

    (dat[v]*=d)%=mod,(sum[v]*=d)%=mod,(add[v]*=d)%=mod,(mul[v]*=d)%=mod;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(unsigned int i=1;i<=n;i++) siz[i]=dat[i]=sum[i]=mul[i]=1;

    for(unsigned int u,v,i=1;i<n;i++)

    {

        scanf("%d%d",&u,&v);

        link(u,v);

    }

    char op[3];

    for(unsigned int u,v,c,i=1;i<=m;i++)

    {

        scanf("%s%d%d",op,&u,&v);

        if(op[0]=='+') scanf("%d",&c),Add(u,v,c);

        else if(op[0]=='-') cat(u,v),scanf("%d%d",&u,&v),link(u,v);

        else if(op[0]=='*') scanf("%d",&c),Mul(u,v,c);

        else printf("%d\n",query(u,v));

    }

    return 0;

}

---

2018.12.7