P3384 轻重链剖分

复杂数据结构++

树链剖分，极大地提高了树上元素的查询修改的效率。

这里是轻重链剖分，通过将对树的dfs，在求出每个节点的父亲，深度，子树大小，重儿子编号的同时，把树分割成了若干条重链，每条链都有独一无二的top节点

然后将这些链逐一标号映射到序列中，在轻重链剖分下每一个节点及其子树的下表在序列中连续。

因此就可以通过线段树之类的数据结构在log级别的时间内修改查询

#pragma GCC optimize(2)
#include
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
double pi = acos(-1);
const double eps = 1e-12;
const int maxn = 1e5 + 10;
const int inf = 1e9;
int read()
{
    int 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 << 1) + (x << 3) + c - '0', c = getchar();
    return f * x;
}
ll a[maxn], wt[maxn], mod;
int n, m, S;
int head[maxn], deep[maxn], fa[maxn], siz[maxn], son[maxn], id[maxn], top[maxn], edge_cnt = 0, cnt = 0;

struct edge {
    int to, next;
}e[2 * maxn];

inline void add(int from, int to)
{
    e[++edge_cnt].to = to;
    e[edge_cnt].next = head[from];
    head[from] = edge_cnt;
}

void dfs1(int now, int f, int dee)//先记录每个点的深度，子树大小，父节点编号，重儿子编号
{
    deep[now] = dee;
    fa[now] = f;
    siz[now] = 1;
    int maxson = -1;
    for (int i = head[now]; i; i = e[i].next)
    {
        int to = e[i].to;
        if (to == f)continue;
        dfs1(to, now, dee + 1);
        siz[now] += siz[to];
        if (siz[to] > maxson)son[now] = to, maxson = siz[to];
    }
}

void dfs2(int now, int topf)
{
    id[now] = ++cnt;
    wt[cnt] = a[now];//将节点值映射到序列
    top[now] = topf;
    if (!son[now])return;
    dfs2(son[now], topf);//先处理重儿子
    for (int i = head[now]; i; i = e[i].next)
    {
        int to = e[i].to;
        if (to == fa[now] || to == son[now])continue;
        dfs2(to, to);//遍历轻儿子，然而轻儿子还是会先遍历重边，所以每一条重链新编号是连续的
    }
    //最终子树的编号也是连续的，因此可以用线段树查询子树和
}

struct tree {
    int ls;
    int rs;
    long long vue = 0;
    long long lazy = 0;
}t[4 * maxn];
void build(int l, int r, int p)
{
    t[p].ls = l;
    t[p].rs = r;
    if (l == r) { t[p].vue = wt[l] % mod; return; }
    int mid = l + r >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, (p << 1) + 1);
    t[p].vue = (t[p << 1].vue + t[(p << 1) + 1].vue) % mod;
}
inline void spread(int x)//标记下传
{
    if (t[x].lazy)//如果该节点标记不为0
    {
        t[x * 2].vue += t[x].lazy * (ll)(t[x * 2].rs - t[x * 2].ls + 1);//更新左子区间和
        t[x * 2 + 1].vue += t[x].lazy * (ll)(t[x * 2 + 1].rs - t[x * 2 + 1].ls + 1);//更新右子区间和
        t[x * 2].lazy += t[x].lazy;
        t[x * 2 + 1].lazy += t[x].lazy;//向子节点传递标记
        t[x].lazy = 0;//初始化标记
    }
}
void update_add(int x, int y, ll v, int p)
{
    ll l = t[p].ls;
    ll r = t[p].rs;
    if (l >= x && r <= y)
    {
        t[p].vue += (long long)v * (r - l + 1);
        t[p].lazy += v;
        return;
    }
    spread(p);
    int mid = l + r >> 1;
    if (x <= mid)update_add(x, y, v, p << 1);
    if (y > mid)update_add(x, y, v, (p << 1) + 1);
    t[p].vue = t[p << 1].vue + t[(p << 1) + 1].vue;
}

long long query(int x, int y, int p)
{
    int l = t[p].ls;
    int r = t[p].rs;
    if (l >= x && r <= y)
    {
        return t[p].vue % mod;
    }
    int mid = l + r >> 1;
    long long ans = 0;
    spread(p);
    if (x <= mid)ans = (ans + query(x, y, p << 1)) % mod;
    if (y > mid)ans = (ans + query(x, y, (p << 1) + 1)) % mod;
    return ans;
}

void update_range(int x, int y,ll v)
{
    v %= mod;
    while (top[x] != top[y])
    {
        if (deep[top[y]] > deep[top[x]])swap(x, y);
        update_add(id[top[x]], id[x], v, 1);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y])swap(x, y);
    update_add(id[x], id[y], v, 1);
}

ll query_range(int x,int y)
{
    ll res = 0;
    while (top[x] != top[y])
    {
        if (deep[top[y]] > deep[top[x]])swap(x, y);
        res = (res + query(id[top[x]], id[x], 1)) % mod;
        x = fa[top[x]];
    }
    if (deep[x] > deep[y])swap(x, y);
    res = (res + query(id[x], id[y], 1)) % mod;
    return res;
}

int main()
{
    fastio;
    cin >> n >> m >> S >> mod;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfs1(S, 0, 1);
    dfs2(S, S);
    build(1, n, 1);
    ll o, x, y, z;
    while (m--)
    {
        cin >> o;
        if (o == 1)
        {
            cin >> x >> y >> z;
            update_range(x, y, z);
        }
        else if (o == 2)
        {
            cin >> x >> y;
            cout << query_range(x, y) << endl;
        }
        else if (o == 3)
        {   
            cin >> x >> z;
            update_add(id[x], id[x] + siz[x] - 1, z, 1);
        }
        else
        {
            cin >> x;
            cout << query(id[x], id[x] + siz[x] - 1, 1) << endl;
        }
    }
    return 0;

}