Rockdu's Blog

题目描述

一棵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行，每行描述一个操作

输出格式：

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

输入输出样例

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

4

说明

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 (伍一鸣)

一道LCT维护树上信息的题，可以当做加强版模板题了。具体操作对于每一个询问或修改，把一个端点变成根，然后access另一个端点就能分离出两点之间的整条路径组成的一颗Splay，直接在这颗Splay的根上打标记就行了。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5, mod = 51061;
char s;
int n, m, a, b, c, d, cnt;
inline char gc(){
    static char buf[2000000], *p1 = buf, *p2 = buf;
    return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0; static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
inline void rc(char & x) {
    x = gc();
    while(x != '+' && x != '-' && x != '*' && x != '/') x = gc();
}
namespace LCT {
    const int L = 0, R = 1;
    struct node {
        int ch[2], fa, rv, size;
        LL sum, mul, add, num;
    }tree[maxn];
    #define isrt(x) (tree[tree[x].fa].ch[R] != x && tree[tree[x].fa].ch[L] != x)
    void init(int n) {
        for(register int i = 1; i <= n; ++i) 
            tree[i].size = 1, tree[i].mul = 1, tree[i].num = 1, tree[i].sum = 1;
    }
    int tl, tr;
    void push_up(int rt) {
        tl = tree[rt].ch[L], tr = tree[rt].ch[R];
        tree[rt].size = tree[tl].size + tree[tr].size + 1;
        tree[rt].sum = (tree[tr].sum + tree[tl].sum + tree[rt].num) % mod;
    }
    void push_down(int rt) {
        if(tree[rt].rv) {
            tree[rt].rv = 0;
            swap(tree[rt].ch[L], tree[rt].ch[R]);
            tree[tree[rt].ch[L]].rv ^= 1;
            tree[tree[rt].ch[R]].rv ^= 1;
        }
        if(tree[rt].mul != 1) {
            tl = tree[rt].ch[L], tr = tree[rt].ch[R];
            tree[tl].mul = tree[rt].mul * tree[tl].mul % mod;
            tree[tr].mul = tree[rt].mul * tree[tr].mul % mod;
            tree[tl].add = tree[rt].mul * tree[tl].add % mod;
            tree[tr].add = tree[rt].mul * tree[tr].add % mod;
            tree[tl].sum = tree[tl].sum * tree[rt].mul % mod;
            tree[tr].sum = tree[tr].sum * tree[rt].mul % mod;
            tree[tl].num = tree[tl].num * tree[rt].mul % mod;
            tree[tr].num = tree[tr].num * tree[rt].mul % mod;
            tree[rt].mul = 1;
        }
        if(tree[rt].add) {
            tl = tree[rt].ch[L], tr = tree[rt].ch[R];
            tree[tl].add = (tree[tl].add + tree[rt].add) % mod;
            tree[tr].add = (tree[tr].add + tree[rt].add) % mod;
            tree[tl].sum = (tree[tl].sum + tree[rt].add * tree[tl].size) % mod;
            tree[tr].sum = (tree[tr].sum + tree[rt].add * tree[tr].size) % mod;
            tree[tl].num = (tree[tl].num + tree[rt].add) % mod;
            tree[tr].num = (tree[tr].num + tree[rt].add) % mod;
            tree[rt].add = 0;
        }
    }
    void rotate(int rt) {
        int p = tree[rt].fa, a = tree[p].fa;
        int r = tree[p].ch[R] == rt, l = r ^ 1;
        if(!isrt(p)) tree[a].ch[tree[a].ch[R] == p] = rt;
        tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[l]].fa = p;
        tree[p].ch[r] = tree[rt].ch[l], tree[rt].ch[l] = p;
        push_up(p), push_up(rt);
    }
    void splay(int rt, int y) {
        int des = tree[y].fa;
        while(tree[rt].fa != des) {
            int p = tree[rt].fa, a = tree[p].fa;
            push_down(a), push_down(p), push_down(rt);
            if(p != y)  if((tree[a].ch[R] == p) ^ (tree[p].ch[R] == rt)) rotate(rt);
                       	  else rotate(p);
            rotate(rt);
        }
    }
    int findrt(int x) {while(!isrt(x))x = tree[x].fa;return x;}
    void change(const int &x, const int &y) {
        int u = findrt(x);
        splay(x, u), push_down(x), tree[x].ch[R] = y;
        push_up(x); /*!!!!!!注意push_up!!!!!!*/
    }
    int access(int x) {
        for(change(x, 0); tree[x].fa; x = tree[x].fa) 
            change(tree[x].fa, x);
        int u = x;
        while(push_down(x), tree[x].ch[L]) x = tree[x].ch[L];
        return splay(x, u), x;
    }
    void makeroot(int x) {tree[access(x)].rv ^= 1;}
    void link(int x, int y) {tree[x = access(x)].rv ^= 1, tree[x].fa = y;}
    void cut(int x, int y) {change(x, 0), change(y, 0), tree[tree[x].fa == y ? x : y].fa = 0;}
    bool isconnect(int x, int y) {return access(x) == access(y);}
    int Qnxt(int x, int type) {
        x = tree[x].ch[type];
        while(tree[x].ch[type ^ 1])
            x = tree[x].ch[type ^ 1]; 
        return x;
    }
    int GetSum(int x, int y) {
        makeroot(y);access(x);
        return tree[findrt(x)].sum;
    }
    void add(int x, int y, int dt) {
        makeroot(y), access(x);
        int rt = findrt(x);
        (tree[rt].add += dt) %= mod;
        (tree[rt].sum += tree[rt].size * dt * 1LL) %= mod;
        (tree[rt].num += dt) %= mod;
    }
    void mul(int x, int y, int dt) {
        makeroot(y), access(x);
        int rt = findrt(x);
        (tree[rt].mul *= dt) %= mod;
        (tree[rt].add *= dt) %= mod;
        (tree[rt].sum *= dt) %= mod;
        (tree[rt].num *= dt) %= mod;
    }
}

int main() {
    read(n), read(m), LCT::init(n);
    for(register int i = 1; i < n; ++i) {
        read(a), read(b);
        LCT::link(a, b);
    }
    for(register int i = 1; i <= m; ++i) {
        rc(s);
        if(s == '+') read(a), read(b), read(c), LCT::add(a, b, c);
        else if(s == '-') read(a), read(b), read(c), read(d), LCT::cut(a, b), LCT::link(c, d);
        else if(s == '/') read(a), read(b), printf("%d\n", LCT::GetSum(a, b));
        else if(s == '*') read(a), read(b), read(c), LCT::mul(a, b, c);
    }
    return 0;
}