luogu1501 [国家集训队]Tree II

佚名 4年前 (2020-02-26) 算法 722人围观抢沙发百度已收录

题目链接

problem

给出一棵有点权的树，支持4种操作。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

路径加
路径乘
删除一条边并添加一条边，操作后还是一棵树
求路径和

solution

删边和添边的操作可以用LCT解决。
路径加和路径乘再splay上打标记即可。
下方的时候要按照一定的顺序下方。下面的代码是先下放乘法标记，下放乘法标记的时候需要将加法标记一起乘。

code

/*
* @Author: wxyww
* @Date: 2020-02-25 17:55:05
* @Last Modified time: 2020-02-25 20:22:06
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uin;
const int N = 100010,mod = 51061;
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    uin pre,ch[2],val,sum,lazy1,lazy2,siz,rev;
}TR[N];
void up(int cur) {
    TR[cur].sum = (TR[ls].sum + TR[rs].sum + TR[cur].val) % mod;
    TR[cur].siz = TR[ls].siz + TR[rs].siz + 1;
}
void pushdown(int cur) {

    if(TR[cur].lazy1 != 1) {//lazy1是乘法标记
        uin tmp = TR[cur].lazy1;
        TR[ls].lazy1 = TR[ls].lazy1 * tmp % mod;
        TR[rs].lazy1 = TR[rs].lazy1 * tmp % mod;
        TR[ls].lazy2 = TR[ls].lazy2 * tmp % mod;
        TR[rs].lazy2 = TR[rs].lazy2 * tmp % mod;
        TR[ls].sum = TR[ls].sum * tmp % mod;
        TR[rs].sum = TR[rs].sum * tmp % mod;
        TR[ls].val = TR[ls].val * tmp % mod;
        TR[rs].val = TR[rs].val * tmp % mod;
        TR[cur].lazy1 = 1;
    }
    if(TR[cur].lazy2) {//lazy2为加法标记
        uin tmp = TR[cur].lazy2;
        TR[ls].lazy2 = (TR[ls].lazy2 + tmp) % mod;
        TR[rs].lazy2 = (TR[rs].lazy2 + tmp) % mod;
        TR[ls].sum = (TR[ls].sum + tmp * TR[ls].siz % mod) % mod;
        TR[rs].sum = (TR[rs].sum + tmp * TR[rs].siz % mod) % mod;
        TR[ls].val = (TR[ls].val + tmp) % mod;
        TR[rs].val = (TR[rs].val + tmp) % mod;
        TR[cur].lazy2 = 0;
    }
    if(TR[cur].rev) {
        TR[ls].rev ^= 1;TR[rs].rev ^= 1;
        swap(ls,rs);
        TR[cur].rev = 0;
    }
}
int isroot(int cur) {
    return TR[TR[cur].pre].ch[0] != cur && TR[TR[cur].pre].ch[1] != cur;
}
int getwh(int cur) {
    return TR[TR[cur].pre].ch[1] == cur;
}
void rotate(int cur) {
    int fa = TR[cur].pre,gr = TR[fa].pre,f = getwh(cur);

    if(!isroot(fa)) TR[gr].ch[getwh(fa)] = cur;
    TR[cur].pre = gr;

    if(TR[cur].ch[f ^ 1]) TR[TR[cur].ch[f ^ 1]].pre = fa;
    TR[fa].ch[f] = TR[cur].ch[f ^ 1];

    TR[fa].pre = cur;TR[cur].ch[f ^ 1] = fa;
    up(fa);up(cur);
}
int sta[N],top;
void splay(int cur) {
    sta[++top] = cur;
    for(int i = cur;!isroot(i);i = TR[i].pre) sta[++top] = TR[i].pre;

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

    while(!isroot(cur)) {
        if(!isroot(TR[cur].pre)) {
            if(getwh(TR[cur].pre) == getwh(cur)) rotate(TR[cur].pre);
            else rotate(cur);
        }
        rotate(cur);
    }
}

void access(int cur) {
    for(int t = 0;cur;t = cur,cur = TR[cur].pre) {
        splay(cur);rs = t;up(cur);
    }
}

void makeroot(int cur) {
    access(cur);splay(cur);
    TR[cur].rev ^= 1;
}
void link(int x,int y) {
    makeroot(x);TR[x].pre = y;
}
void cut(int x,int cur) {
    makeroot(x);access(cur);
    splay(cur);
    ls = TR[ls].pre = 0;
    up(cur);
}

void update2(int x,int y,int c) {//处理加法
    makeroot(x);access(y);splay(y);
    TR[y].sum += c * TR[y].siz % mod;
    TR[y].sum %= mod;
    TR[y].val = (TR[y].val + c) % mod;
    TR[y].lazy2 = (TR[y].lazy2 + c) % mod;
}

void update1(int x,int y,int c) {
    makeroot(x);access(y);splay(y);

    TR[y].sum = TR[y].sum * c % mod;
    TR[y].lazy1 = TR[y].lazy1 * c % mod;
    TR[y].val = TR[y].val * c % mod;
    TR[y].lazy2 = TR[y].lazy2 * c % mod;
}

int query(int x,int y) {
    makeroot(x);access(y);splay(y);
    return TR[y].sum;
}

signed main() {
    int n = read(),Q = read();

    for(int i = 1;i <= n;++i) TR[i].lazy1 = TR[i].val = TR[i].sum = TR[i].siz = 1;

    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        link(u,v);
    }
    while(Q--) {
        char c = getchar();
        while(c != '+' && c != '-' && c != '*' && c != '/') c = getchar();
        if(c == '+') {
            int u = read(),v = read(),w = read();
            update2(u,v,w);
        }
        if(c == '-') {
            int u1 = read(),v1 = read(),u2 = read(),v2 = read();
            cut(u1,v1);link(u2,v2);
        }
        if(c == '*') {
            int u = read(),v = read(),w = read();
            update1(u,v,w);
        }
        if(c == '/') {
            int u = read(),v = read();
            printf("%d\n",query(u,v));
        }
    }

    return 0;
}