BZOJ 2631 tree | Luogu P1501 [国家集训队]Tree II (LCT 多重标记下放）

链接：https://www.luogu.org/problemnew/show/P1501

题面：

题目描述

一棵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：复制

输出样例#1：复制

说明

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

By (伍一鸣)

思路：

写法跟线段树差不多，修改i下pushdown多维护连个标记就好了。

实现代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ls c[x][0]

#define rs c[x][1]

const int M = 4e5+;

const int inf = 1e9;

const int mod = ;

int top;

int sum[M],c[M][],val[M],fa[M],rev[M],mn[M],S[M],tmp[M];

int siz[M],mul[M],add[M];

inline void up(int x){

    //cout<<sum[x]<<" "<<sum[ls]<<" "<<sum[rs]<<" "<<val[x]<<endl;

    sum[x] = (sum[ls] + sum[rs] + val[x])%mod;

    siz[x] = (siz[ls] + siz[rs] + )%mod;;

}

inline void pushrev(int x){

    swap(ls,rs); rev[x] ^= ;

}

inline void pushmul(int x,int c){

    mul[x] = (1LL*mul[x]*c)%mod;

    add[x] = (1LL*add[x]*c)%mod;

    sum[x] = (1LL*sum[x]*c)%mod;

    val[x] = (1LL*val[x]*c)%mod;

    //cout<<mul[x]<<" "<<val[x]<<endl;

}

inline void pushadd(int x,int c){

    add[x] = (add[x] + c)%mod;

    val[x] = (val[x] + c)%mod;

    sum[x] = (1LL*sum[x]+1LL*siz[x]*c)%mod;

}

inline bool isroot(int x){

    return c[fa[x]][]!=x&&c[fa[x]][]!=x;

}

inline void rotate(int x){

    int y = fa[x],z = fa[y];

    int k = c[y][] == x;

    if(!isroot(y)) c[z][c[z][]==y]=x;

    fa[x] = z;

    c[y][k] = c[x][k^]; fa[c[x][k^]] = y;

    c[x][k^] = y; fa[y] = x;

    up(y); up(x);

}

inline void pushdown(int x){

    if(rev[x]){

        if(ls) pushrev(ls);

        if(rs) pushrev(rs);

        rev[x] = ;

    }

    if(mul[x]!=){

        if(ls) pushmul(ls,mul[x]);

        if(rs) pushmul(rs,mul[x]);

        mul[x] = ;

    }

    if(add[x]){

        if(ls) pushadd(ls,add[x]);

        if(rs) pushadd(rs,add[x]);

        add[x] = ;

    }

}

inline void splay(int x){

    S[top=]=x;

    for(int i = x;!isroot(i);i=fa[i]) S[++top] = fa[i];

    while(top) pushdown(S[top--]);

    while(!isroot(x)){

        int y = fa[x],z = fa[y];

        if(!isroot(y))

            (c[y][]==x)^(c[z][]==y)?rotate(x):rotate(y);

        rotate(x);

    }

}

inline void access(int x){

    for(int y = ;x;y = x,x = fa[x])

        splay(x),c[x][] = y,up(x);

}

inline void makeroot(int x){

    access(x); splay(x); pushrev(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] = c[y][] = ; up(y);

}

inline int findroot(int x){

    access(x); splay(x);

    while(ls) x = ls;

    return x;

}

int main()

{

    int n,q,u,v,x,y,k;

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

    for(int i = ;i <= n;i ++) val[i] = mul[i] = ;

    for(int i = ;i < n;i ++){

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

        link(u,v);

    }

    char op[];

    while(q--){

        scanf("%s",op);

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

        if(op[] == '+') {

            scanf("%d",&k);

            split(u,v); pushadd(v,k);

        }

        else if(op[] == '-'){

            scanf("%d%d",&x,&y);

            cut(u,v); link(x,y);

        }

        else if(op[] == '*'){

            scanf("%d",&k);

            split(u,v); pushmul(v,k);

        }

        else if(op[] == '/'){

            //cout<<u<<" "<<v<<endl;

            split(u,v); printf("%d\n",sum[v]);

        }

    }

    return ;

}

巴特西

BZOJ 2631 tree | Luogu P1501 [国家集训队]Tree II (LCT 多重标记下放）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章