如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一 个数值, 需要支持以下操作 :
操作1 :格式: 1 x y z表示将树从x到y结点最短路径上所有节点的值都加上z
操作2 :格式: 2 x y表示求树从x到y结点最短路径上所有节点的值之和
操作3:格式: 3 x z表示将以为根节点的子树内所有节点值都加上z
操作4:格式: 4 x表示求以x为根节点的子树内所有节点值之和

国家集训队的题的时候发现打炸了
感觉自己树剖有点问题
所以又跑过去刷刷树剖
这么简单的东西就不写多了

代码:

#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define mid ((l+r)>>1)
#define len (r-l+1)
using namespace std;

int n,m,root,mod,u,v,w,opt,x,y,z;
int a[N];

struct Edge
{
    int next,to;
}edge[N<<1];
int cnt=0,head[N];

inline void add_edge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

/*树链剖分的两个dfs*/

int dep[N],fa[N],size[N],son[N];
void dfs1(int u,int f)
{
    fa[u]=f;
    size[u]=1;
    dep[u]=dep[f]+1;
    for(register int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==f) continue;
        dfs1(v,u);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

int seg[N],rev[N],top[N];
void dfs2(int u)
{
    int v=son[u];
    if(v)
    {
        seg[v]=++seg[0];//每个点新的编号
        rev[seg[0]]=v;
        top[v]=top[u];//这个点所在链的顶端
        dfs2(v);
    }
    for(register int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!top[v])
        {
            seg[v]=++seg[0];
            rev[seg[0]]=v;
            top[v]=v;
            dfs2(v);
        }
    }
}

/*线段树部分*/

int sum[N<<2],add[N<<2];

void pushup(int rt) {sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;}//向上更新线段树

void add_add(int rt,int l,int r,int v)//加法标记更新
{
    add[rt]=(add[rt]+v)%mod;
    sum[rt]=(sum[rt]+v*len)%mod;
}

void pushdown(int rt,int l,int r)//标记下放
{
    if(!add[rt]) return;
    add_add(rt<<1,l,mid,add[rt]);
    add_add(rt<<1|1,mid+1,r,add[rt]);
    add[rt]=0;//记得清零
}

void modify(int rt,int l,int r,int x,int y,int v)//调整
{
    if(l>y||r<x) return;
    if(x<=l&&y>=r)
    {
        add_add(rt,l,r,v);
        return;
    }
    pushdown(rt,l,r);
    modify(rt<<1,l,mid,x,y,v);
    modify(rt<<1|1,mid+1,r,x,y,v);
    pushup(rt);
}

int query(int rt,int l,int r,int x,int y)//求和
{
    if(l>y||r<x) return 0;
    if(x<=l&&y>=r) return sum[rt]%mod;
    pushdown(rt,l,r);
    return ( query(rt<<1,l,mid,x,y) + query(rt<<1|1,mid+1,r,x,y) )%mod;
}

void build(int rt,int l,int r)//建树
{
    if(l==r)
    {
        sum[rt]=a[rev[l]];
        return;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

/*主体部分*/

void modify_edge(int x,int y,int v)//链修改
{
    int fx=top[x];
    int fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])
        {
            swap(fx,fy);
            swap(x,y);
        }
        modify(1,1,seg[0],seg[fx],seg[x],v);
        x=fa[fx];
        fx=top[x];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1,1,seg[0],seg[x],seg[y],v);
}

int ask_edge(int x,int y)//链查询
{
    int fx=top[x];
    int fy=top[y];
    int res=0;
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])
        {
            swap(fx,fy);
            swap(x,y);
        }
        res=(res+query(1,1,seg[0],seg[fx],seg[x]))%mod;
        x=fa[fx];
        fx=top[x];
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=(res+query(1,1,seg[0],seg[x],seg[y]))%mod;
    return res;
}

void modify_tree(int rt,int v)//树修改
{
    modify(1,1,seg[0],seg[rt],seg[rt]+size[rt]-1,v%mod);
}

int ask_tree(int rt)//树查询
{
    return query(1,1,seg[0],seg[rt],seg[rt]+size[rt]-1)%mod;
}

void init()
{
    seg[0]=seg[root]=1;
    top[root]=root;
    rev[1]=root;
    dfs1(root,0);
    dfs2(root);
    build(1,1,seg[0]);
}

int main()
{
    read(n);read(m);read(root);read(mod);
    for(register int i=1;i<=n;++i) read(a[i]),a[i]%=mod;
    for(register int i=1;i<=n-1;++i)
    {
        read(u);read(v);
        add_edge(u,v);
        add_edge(v,u);
    }
    init();
    for(register int i=1;i<=m;++i)
    {
        read(opt);
        if(opt==1)//链增加
        {
            read(x);read(y);read(z);
            modify_edge(x,y,z);
        }
        else if(opt==2)//链查询最小值
        {
            read(x);read(y);
            printf("%d\n",ask_edge(x,y));
        }
        else if(opt==3)//树增加
        {
            read(x);read(z);
            modify_tree(x,z);
        }
        else if(opt==4)//树求和
        {
            read(x);
            printf("%d\n",ask_tree(x));
        }
    }
    return 0;
}
/*
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/
02-11 19:00