题目链接

//部分转自：https://www.luogu.org/problemnew/solution/P3384

Beginner tree chain division,I feel that this template question is easy to understand,But it's really huge.

知识点：

• 重儿子：对于每一个非叶子节点,among its sons The one with the largest number of sons is the heavy son of this node
• 轻儿子：对于每一个非叶子节点,among its sons non-heavy son All remaining sons are called light sons
• 叶子节点没有重儿子也没有轻儿子（Because it has no son..）
• 重边：An edge connecting any two heavy children is called a heavy edge
• 轻边：The rest is the light edge
• 重链：相邻重边连起来的 连接一条重儿子 的链叫重链
• 对于叶子节点,If it is a light son,Then there is a length with itself as the starting point1的链
• Every heavy chain starts with a light son
• (太智能了,A picture pops up,

The first is through twodfsto process the information

dfs1()

这个dfsThere are a few things to deal with：

• 标记每个点的深度dep[]
• 标记每个点的父亲fa[]
• 标记每个非叶子节点的子树大小(contains itself)
• 标记每个非叶子节点的重儿子编号son[]

void dfs1(int u,int pre,int dep)
{
    f[u]=pre;
    d[u]=dep;
    size[u]=1;
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs1(v,u,dep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])
            son[u]=v;
    }
}

dfs2()

这个dfs2There are a few things to preprocess as well

• 标记每个点的新编号
• Assign the initial value of each point to the new number
• Process the top of the chain where each point is
• Process each chain

void dfs2(int u,int tp)
{
    top[u]=tp;
    dfn[u]=++t;
    tim[t]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v!=f[u]&&v!=son[u]) dfs2(v,v);
    }
}

顺序：Deal with the heavy son first and then deal with the light

Probably the most important process is these two,Divided by light and heavy son（Deal with the heavy son first and then deal with the light）First, its tree structure can be converted into a linear structure,Used for line segment trees to handle various on-tree information,但是不同于dfstraverse directly in order,The new number after the tree chain is split,In most query processing intervals are continuous intervals,In fact, it is to split the tree into individual chains,Then elegant(baoli)of solving various problems.

代码：

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
//const int mod=1e9+7;
const int maxn=2e5+5;
int d[maxn];//深度
int son[maxn];//The heavy son of a certain point
int top[maxn];//The point is at the head of the chain
int dfn[maxn];//Timestamp of a point
int tim[maxn];//Record the node subscript corresponding to a timestamp
int a[maxn];//Node initial weight
int size[maxn];//The number of subtrees rooted at the point（包括自己
int f[maxn];//前驱
int head[maxn],sign,t;
int n,root,q,mod;
int tree[maxn<<2],lazy[maxn<<2];
struct node
{
    int to,p;
}edge[maxn<<1];
void init()
{
    for(int i=0;i<=n;i++) head[i]=-1;
    sign=t=0;
}
void add(int u,int v)
{
    edge[sign]=node{v,head[u]};
    head[u]=sign++;
}
void dfs1(int u,int pre,int dep)
{
    f[u]=pre;
    d[u]=dep;
    size[u]=1;
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs1(v,u,dep+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    dfn[u]=++t;
    tim[t]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];~i;i=edge[i].p)
    {
        int v=edge[i].to;
        if(v!=f[u]&&v!=son[u]) dfs2(v,v);
    }
}
void pushup(int i,int l,int r)
{
    tree[i]=(tree[lson]+tree[rson])%mod;
}
void pushdown(int i,int l,int r)
{
    if(lazy[i])
    {
        int mid=half;
        tree[lson]+=(mid-l+1)*lazy[i];
        tree[rson]+=(r-mid)*lazy[i];
        lazy[lson]+=lazy[i];
        lazy[rson]+=lazy[i];
        lazy[i]=0;
    }
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        tree[i]=a[tim[l]];
        return;
    }
    int mid=half;
    build(Lson);
    build(Rson);
    pushup(myself);
}
void update(int i,int l,int r,int ql,int qr,int val)
{
    if(ql<=l&&qr>=r)
    {
        tree[i]+=val*(r-l+1);
        lazy[i]+=val;
        return;
    }
    int mid=half;
    pushdown(myself);
    if(qr<=mid) update(Lson,ql,qr,val);
    else if(ql>mid) update(Rson,ql,qr,val);
    else update(Lson,ql,mid,val),update(Rson,mid+1,qr,val);
    pushup(myself);
}
int query(int i,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r) return tree[i]%mod;
    pushdown(myself);
    int mid=half;
    if(qr<=mid) return query(Lson,ql,qr);
    else if(ql>mid) return query(Rson,ql,qr);
    else return query(Lson,ql,mid)+query(Rson,mid+1,qr);
}
void solve1(int x,int y,int val)//把x,yThe simple path to addval,解释如下
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        update(1,1,n,dfn[top[x]],dfn[x],val);
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    update(1,1,n,dfn[x],dfn[y],val);
}
int solve2(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])//当两个点不在同一条链上
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);//把xDefined as a point with a relatively deep depth,Let him jump up
        ans=(ans+query(1,1,n,dfn[top[x]],dfn[x]))%mod;//ans加上x点到x所在链顶端 这一段区间的点权和
        x=f[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
    }
    if(d[x]>d[y]) swap(x,y);//At this point two o'clock is on a chain
    ans=(ans+query(1,1,n,dfn[x],dfn[y]))%mod;//A chain is a direct interval sum
    return ans;
}
void solve3(int x,int val)//put that point
{
    update(1,1,n,dfn[x],dfn[x]+size[x]-1,val);
}
int solve4(int x)
{
    return query(1,1,n,dfn[x],dfn[x]+size[x]-1)%mod;
}
int main()
{
//    freopen("E://testdata.in","r",stdin);
//    freopen("E://1.out","w",stdout);
    cin>>n>>q>>root>>mod;
    init();
    int x,y,op,val;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=a[i]%mod;
    for(int i=1;i<n;i++)
        scanf("%d %d",&x,&y),add(x,y),add(y,x);
    dfs1(root,0,1);
    dfs2(root,root);
    build(1,1,n);
    while(q--)
    {
        scanf("%d",&op);
        if(op==1) {scanf("%d %d %d",&x,&y,&val);solve1(x,y,val%mod);}
        else if(op==2) {scanf("%d %d",&x,&y);printf("%d\n",solve2(x,y));}
        else if(op==3) {scanf("%d %d",&x,&val);solve3(x,val%mod);}
        else {scanf("%d",&x);printf("%d\n",solve4(x));}
    }
}