洛谷 P1501 [国家集训队]Tree II 题解【LCT】【splay】

点击量：180

第一次写路径加/乘的lct，多存了两个lazytag。

目录

题目描述

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

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

输入输出格式

输入格式：

第一行两个整数$ n,q$

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

接下来$ q$行，每行描述一个操作

输出格式：

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

输入输出样例

输入样例#1：

3 2
1 2
2 3
* 1 3 4
/ 1 1

输出样例#1：

4

说明

$ 10\%$的数据保证，$ 1\le n,q\le 2000$

另外$ 15\%$的数据保证，$ 1\le n,q\le 5\times 10^4$，没有-操作，并且初始树为一条链

另外$ 35\%$的数据保证，$ 1\le n,q\le 5\times 10^4$，没有-操作

$ 100\%$的数据保证，$ 1\le n,q\le 10^5$，$ 0\le c\le 10^4$

题解：

经典的lct操作。主要是维护路径加和路径乘比较麻烦。

这个题目由于存在-操作，所以必须使用lct来完成。但是一个比较麻烦的事情是“对路径上所有点的点权乘上自然数$ c$”，这时我们想起了洛谷的板子洛谷 P3373 【模板】线段树 2。在这个题中我们用两个lazytag维护了线段树（区间）上的加乘混合运算，可以把相似的思想套用到这道题上。

由于这道题在splay上完成，同时splay还有翻转操作，这时就需要存3个lazytag。此时要注意pushdown的操作顺序：区间翻转可以放在任何一个位置，但是乘标记和加标记必须先乘再加，打标记的原理可以看另一篇区间乘线段树的题解，重点在于乘的时候也要对加标记做乘法。

其余的操作就和lct一样了。

btw:不开long long当场去世

lct的题码量真的不大。

Code：

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
#define p 51061
#define ll long long
int ch[2][100100],fa[100100];
ll lazy[100100],lazy1[100100],lazy2[100100],key[100100],sum[100100],sz[100100];
void pushdown(int k)
{
    if(lazy[k])
    {
        int tmp=ls;
        ls=rs;
        rs=tmp;
        lazy[ls]^=1;
        lazy[rs]^=1;
        lazy[k]=0;
    }
    if(lazy2[k]!=1)
    {
        ll x=lazy2[k];
        lazy2[k]=1;
        //修改左右儿子(自己已被修改)
        key[ls]=key[ls]*x%p;
        sum[ls]=sum[ls]*x%p;
        lazy1[ls]=lazy1[ls]*x%p;
        lazy2[ls]=lazy2[ls]*x%p;
        key[rs]=key[rs]*x%p;
        sum[rs]=sum[rs]*x%p;
        lazy1[rs]=lazy1[rs]*x%p;
        lazy2[rs]=lazy2[rs]*x%p;
    }
    if(lazy1[k])
    {
        ll x=lazy1[k];
        lazy1[k]=0;

        key[ls]=(key[ls]+x)%p;
        sum[ls]=(sum[ls]+sz[ls]*x%p)%p;
        lazy1[ls]=(lazy1[ls]+x)%p;
        key[rs]=(key[rs]+x)%p;
        sum[rs]=(sum[rs]+sz[rs]*x%p)%p;
        lazy1[rs]=(lazy1[rs]+x)%p;
    }
}
void maintain(int k)
{
    pushdown(k);
    sum[k]=(sum[ls]+key[k]+sum[rs])%p;
    sz[k]=(sz[ls]+1+sz[rs])%p;
}
void Rotate(int k)
{
    int y=fa[k];
    if(!isroot(y))
        ch[which(y)][fa[y]]=k;
    bool d=which(k);
    fa[k]=fa[y];
    fa[y]=k;
    ch[d][y]=ch[!d][k];
    ch[!d][k]=y;
    fa[ch[d][y]]=y;
    maintain(y);
    maintain(k);
}
int stk[100100],tp=0;
void splay(int k)
{
    while(!isroot(k))
    {
        stk[++tp]=k;
        k=fa[k];
    }
    stk[++tp]=k;
    while(tp)
        pushdown(stk[tp--]);
    k=stk[1];

    while(!isroot(k))
    {
        int y=fa[k];
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)
{
    for(int x=k,y=0;x;y=x,x=fa[x])
    {
        splay(x);
        ch[1][x]=y;
        maintain(x);
    }
}
void makeroot(int k)
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    fa[x]=ch[0][y]=0;
}
char op[100];
int main()
{
    int n,m,u,v,w,x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        key[i]=1,sum[i]=1,lazy2[i]=1,sz[i]=1;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        if(op[0]=='+')
        {
            scanf("%d%d%d",&u,&v,&w);
            split(u,v);
            key[v]=(key[v]+w)%p;
            lazy1[v]=(lazy1[v]+w)%p;
            pushdown(v);
            maintain(v);
        }
        else if(op[0]=='-')
        {
            scanf("%d%d%d%d",&u,&v,&w,&x);
            cut(u,v);
            link(w,x);
        }
        else if(op[0]=='*')
        {
            scanf("%d%d%d",&u,&v,&w);
            split(u,v);
            key[v]=key[v]*w%p;
            lazy1[v]=lazy1[v]*w%p;
            lazy2[v]=lazy2[v]*w%p;
            pushdown(v);
            maintain(v);
        }
        else
        {
            scanf("%d%d",&u,&v);
            split(u,v);
            printf("%lld\n",sum[v]);
        }
    }
    return 0;
}