重链剖分37ptsWA+TLE求条

rt，

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100004;
int n, q, root;
long long mod;
struct node
{
    int depth, size, son, fa, chain;
    long long val;
};
node graph[maxn];
vector<int> to[maxn];
int vis[maxn];

void dfs1(int u)
{
    if(vis[u]) return;
    vis[u] = 1;
    graph[u].size = 1;
    for(int v : to[u])
    {
        if(vis[v]) continue;
        graph[v].depth = graph[u].depth + 1;
        graph[v].fa = u;
        dfs1(v);
        graph[u].size += graph[v].size;
        if(graph[v].size > graph[graph[u].son].size)
            graph[u].son = v; 
    }
} 

struct chn
{
    int head, depth;
};
chn chain[maxn];
vector<int> cto[maxn]; // directed
int dfn[maxn], pos[maxn];
int ccnt = 0, gcnt = 0;
void dfs2(int u)
{
    if(vis[u] || u<=0) return;
    if(graph[u].chain == 0)
    {
        chain[++ccnt].head = u;
        graph[u].chain = ccnt;
        if(ccnt != 1)
        {
            cto[graph[graph[u].fa].chain].push_back(ccnt);
            chain[ccnt].depth = chain[graph[graph[u].fa].chain].depth + 1;
        }
        else chain[ccnt].depth = 0;
    }
    vis[u] = 1;
    dfn[u] = ++gcnt; 
    pos[gcnt] = u;
    graph[graph[u].son].chain = graph[u].chain;
    dfs2(graph[u].son);
    for(int v : to[u])
    {
        if(vis[v]) continue;
        dfs2(v);
    }
}

struct nd
{
    int l, r;
    long long val, lazy;
    inline int len() { return r-l+1; }
};
nd segt[4*maxn];

inline int fa(int u) { return u>>1; }
inline int lc(int u) { return u<<1; }
inline int rc(int u) { return u<<1|1; }

void push_up(int cur)
{
    segt[cur].val = segt[lc(cur)].val + segt[rc(cur)].val;
}

void push_down(int cur)
{
    segt[lc(cur)].val += segt[lc(cur)].len() * segt[cur].lazy;
    segt[rc(cur)].val += segt[rc(cur)].len() * segt[cur].lazy;
    segt[lc(cur)].lazy += segt[cur].lazy;
    segt[rc(cur)].lazy += segt[cur].lazy;
    segt[cur].lazy = 0;
}

void build(int cur, int l, int r)
{
    segt[cur].l = l;
    segt[cur].r = r;
    if(l == r)
    {
        segt[cur].val = graph[pos[l]].val;
        // printf("build(%d, %d, %d) reached leaf: %d\tdfn=%d -> id=%d\n", cur, l, r, graph[pos[l]].val, l, pos[l]);
        return;
    }
    int mid = (l+r)/2;
    build(lc(cur), l, mid);
    build(rc(cur), mid+1, r);
    push_up(cur);
}

long long query(int cur, int l, int r)
{
    if(cur == 1 && l > r) swap(l, r);
    // printf("query(%d, %d, %d)\n", cur, l, r);
    if(segt[cur].l > r || segt[cur].r < l) return 0;
    if(l <= segt[cur].l && segt[cur].r <= r) return segt[cur].val;
    int mid = (segt[cur].l + segt[cur].r) / 2;
    long long ret = 0;
    push_down(cur);
    if(l <= mid) ret += query(lc(cur), l, r);
    if(r > mid) ret += query(rc(cur), l, r);
    return ret;
}

void update(int cur, int l, int r, long long k)
{
    if(cur == 1 && l > r) swap(l, r);
    // printf("update(%d, %d, %d, %lld)\n", cur, l, r, k);
    if(segt[cur].l > r || segt[cur].r < l) return;
    if(l <= segt[cur].l && segt[cur].r <= r)
    {
        segt[cur].val += segt[cur].len() * k;
        segt[cur].lazy += k;
        return;
    }
    int mid = (segt[cur].l + segt[cur].r) / 2;
    push_down(cur);
    if(l <= mid) update(lc(cur), l, r, k);
    if(r > mid) update(rc(cur), l, r, k);
    push_up(cur); 
}

long long query_size(int u)
{
    return query(1, dfn[u], dfn[u] + graph[u].size - 1);
}

void update_size(int u, long long k)
{
    update(1, dfn[u], dfn[u] + graph[u].size - 1, k);
} 

int lca(int u, int v)
{
    if(graph[u].chain == graph[v].chain)
    {
        if(dfn[u] < dfn[v]) return u;
        else return v;
    }
    if(chain[graph[u].chain].depth > chain[graph[v].chain].depth) return lca(graph[u].fa, v);
    else return lca(graph[v].fa, u);
}

long long query_path(int u, int v)
{
    if(graph[u].chain == graph[v].chain)
    {
        if(dfn[u] < dfn[v]) return query(1, dfn[u], dfn[v]);
        else return query(1, dfn[v], dfn[u]);
    }
    long long ret = 0;
    //if(chain[graph[u].chain].depth > chain[graph[v].chain].depth)
    if(graph[chain[graph[u].chain].head].depth > graph[chain[graph[v].chain].head].depth)
        ret += query_path(graph[u].fa, v) + query(1, dfn[u], dfn[chain[graph[u].chain].head]);
    else ret += query_path(graph[v].fa, u) + query(1, dfn[v], dfn[chain[graph[v].chain].head]);
    return ret;
}

void update_path(int u, int v, long long k)
{
    if(graph[u].chain == graph[v].chain)
    {
        if(dfn[u] < dfn[v]) update(1, dfn[u], dfn[v], k);
        else update(1, dfn[v], dfn[u], k);
        return; 
    }
    if(graph[chain[graph[u].chain].head].depth > graph[chain[graph[v].chain].head].depth)
    {
        update(1, dfn[u], dfn[chain[graph[u].chain].head], k);
        update_path(graph[u].fa, v, k);
    }
    else 
    {
        update(1, dfn[v], dfn[chain[graph[v].chain].head], k);
        update_path(graph[v].fa, u, k);
    }
}

// node的fa是它图上的父亲，son是重儿子，chain是所属的那一条链；
// chn的head是链头的节点，cto[]是以链为节点建的图

int main()
{
    scanf("%d%d%d%lld", &n, &q, &root, &mod);
    for(int i=1;i<=n;i++) scanf("%lld", &graph[i].val);
    for(int i=1;i<=n-1;i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        to[u].push_back(v);
        to[v].push_back(u);
    }
    dfs1(root);
    for(int i=0;i<=n;i++) vis[i] = 0;
    dfs2(root);
    /*
    for(int i=1;i<=n;i++)
    {
        printf("Node %d: dfn=%d, val=%d, fa=%d, son=%d, chain=%d\t\tsize=%d, depth=%d;\tpos[%d]=%d\n",
            i, dfn[i], graph[i].val, graph[i].fa, graph[i].son, graph[i].chain, graph[i].size, graph[i].depth, i, pos[i]);
    }
    printf("\n");
    for(int i=1;i<=ccnt;i++)
    {
        printf("Chain %d: head=%d, depth=%d\n",
            i, chain[i].head, chain[i].depth);
    }
    */ 
    build(1, 1, n);

    // for(int i=1;i<=n;i++) printf("segt[%d].val = %d as %d in query\n", i, segt[i].val, query(1, i, i));
    // for(int i=1;i<=n;i++) printf("segt[%d].val = %d\n", i, segt[i].val);

    while(q--)
    {
        int opt, x, y;
        long long z;
        scanf("%d", &opt);
        if(opt == 1)
        {
            scanf("%d%d%lld", &x, &y, &z);
            update_path(x, y, z); 
        }
        if(opt == 2)
        {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query_path(x, y) % mod);
        }
        if(opt == 3)
        {
            scanf("%d%lld", &x, &z);
            update_size(x, z);
        }
        if(opt == 4)
        {
            scanf("%d", &x);
            printf("%lld\n", query_size(x) % mod);
        }
        if(opt == 5)
        {
            scanf("%d%d", &x, &y);
            printf("LCA of (%d, %d) = %d\n", x, y, lca(x, y));
        }
    }
    return 0;
}

https://www.luogu.com.cn/record/194602471