【洛谷1501】[国家集训队] Tree II（LCT维护懒惰标记）

点此看题面

大致题意： 有一棵初始边权全为\(1\)的树，四种操作：将两点间路径边权都加上一个数，删一条边、加一条新边，将两点间路径边权都加上一个数，询问两点间路径权值和。

序列版

这道题有一个序列版：【洛谷3373】【模板】线段树 2。

看题目就知道是一道线段树板子题。

这种题目移到树上路径中，且要删边加边，是\(LCT\)无疑了。

\(LCT\)维护懒惰标记

可以说，这道题就是上面那题的翻版。

同样维护两个标记：乘法标记和加法标记，加上原有的翻转标记，共三个标记。

具体细节其实可以详见上面提到的那道线段树板子题，这里就不多说了。

主要是要注意标记下传与更新的优先级问题，应该是乘法先，加法后，至于翻转标记在前在后都无所谓。

代码

#include<bits/stdc++.h>
#define N 100000
#define MOD 51061
#define swap(x,y) (x^=y^=x^=y)
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
using namespace std;
int n,ee,lnk[N+5];
class Class_FIO
{
    private:
        #define Fsize 100000
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
        #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))
        int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];
    public:
        Class_FIO() {A=B=Fin;}
        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
        inline void readc(char &x) {while(isspace(x=tc()));}
        inline void writeln(int x) {while(Stack[++Top]=x%10+48,x/=10);while(Top) pc(Stack[Top--]);pc('\n');}
        inline void clear() {fwrite(Fout,1,FoutSize,stdout),FoutSize=0;}
}F;
class Class_LCT//LCT板子
{
    private:
        #define LCT_SIZE N
        #define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+1,node[x].Sum=(node[x].Val+node[node[x].Son[0]].Sum+node[node[x].Son[1]].Sum)%MOD)
        #define MulVal(x,v) (node[x].Sum=1LL*node[x].Sum*v%MOD,node[x].Val=1LL*node[x].Val*v%MOD,node[x].flag1=1LL*node[x].flag1*v%MOD,node[x].flag2=1LL*node[x].flag2*v%MOD)
        #define AddVal(x,v) (Inc(node[x].Sum,1LL*node[x].Size*v%MOD),Inc(node[x].Val,v),Inc(node[x].flag2,v))
        #define Rever(x) (swap(node[x].Son[0],node[x].Son[1]),node[x].Rev^=1)
        #define PushDown(x)        (            node[x].flag1^1&&(MulVal(node[x].Son[0],node[x].flag1),MulVal(node[x].Son[1],node[x].flag1),node[x].flag1=1),            node[x].flag2&&(AddVal(node[x].Son[0],node[x].flag2),AddVal(node[x].Son[1],node[x].flag2),node[x].flag2=0),            node[x].Rev&&(Rever(node[x].Son[0]),Rever(node[x].Son[1]),node[x].Rev=0)        )
        #define Which(x) (node[node[x].Father].Son[1]==x)
        #define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)
        #define IsRoot(x) (node[node[x].Father].Son[0]^x&&node[node[x].Father].Son[1]^x)
        #define MakeRoot(x) (Access(x),Splay(x),Rever(x))
        #define Split(x,y) (MakeRoot(x),Access(y),Splay(y)) 
        int Stack[LCT_SIZE+5];
        struct Tree
        {
            int Val,Sum,Size,flag1,flag2,Rev,Father,Son[2];
        }node[LCT_SIZE+5];
        inline void Rotate(int x)
        {
            register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);
            !IsRoot(fa)&&(node[pa].Son[Which(fa)]=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);
        }
        inline void Splay(int x)
        {
            register int fa=x,Top=0;
            while(Stack[++Top]=fa,!IsRoot(fa)) fa=node[fa].Father;
            while(Top) PushDown(Stack[Top]),--Top;
            while(!IsRoot(x)) fa=node[x].Father,!IsRoot(fa)&&(Rotate(Which(x)^Which(fa)?x:fa),0),Rotate(x);
        }
        inline void Access(int x) {for(register int son=0;x;x=node[son=x].Father) Splay(x),node[x].Son[1]=son,PushUp(x);}
        inline int FindRoot(int x) {Access(x),Splay(x);while(node[x].Son[0]) PushDown(x),x=node[x].Son[0];return Splay(x),x;}
    public:
        inline void Init(int len) {for(register int i=1;i<=len;++i) node[i].Val=node[i].flag1=1;}
        inline void Link(int x,int y) {MakeRoot(x),FindRoot(y)^x&&(node[x].Father=y);}
        inline void Cut(int x,int y) {MakeRoot(x),!(FindRoot(y)^x)&&!(node[y].Father^x)&&!node[y].Son[0]&&(node[y].Father=node[x].Son[1]=0,PushUp(x));}
        inline void Mul(int x,int y,int v) {Split(x,y),MulVal(y,v);}
        inline void Add(int x,int y,int v) {Split(x,y),AddVal(y,v);}
        inline int Query(int x,int y) {return Split(x,y),node[y].Sum;}
}LCT;
int main()
{
    register int query_tot,i,x,y,z;register char op;
    for(F.read(n),F.read(query_tot),LCT.Init(n),i=1;i<n;++i) F.read(x),F.read(y),LCT.Link(x,y);
    while(query_tot--)
    {
        F.readc(op),F.read(x),F.read(y);
        switch(op)
        {
            case '*':F.read(z),LCT.Mul(x,y,z);break;
            case '+':F.read(z),LCT.Add(x,y,z);break;
            case '-':LCT.Cut(x,y),F.read(x),F.read(y),LCT.Link(x,y);break;
            case '/':F.writeln(LCT.Query(x,y));break;
        }
    }
    return F.clear(),0;
}

【洛谷1501】[国家集训队] Tree II（LCT维护懒惰标记）

原文：https://www.cnblogs.com/chenxiaoran666/p/Luogu1501.html