树链剖分。

快把我脑袋都要剖开了。

这是一个省选知识的模板。但是NOIP2016年还是考了天天爱跑步这种省选难度的题。

但我不知道为啥还是有人会AK

这个算法呢,就是首先深搜两遍

第一遍深搜是为了建树,记录父亲节点fa、子树的重量size、深度dep、还有重儿子hson。

这里提一下重儿子的概念,就是你这个节点有很多子树,其中某个子树的重量(就是该子树的节点数)最大,我们称他为重儿子。

第二遍深搜是为了分链,重新编号id,记录链顶top。

这里如何分链呢,首先你要从根开始将重儿子找出来,然后重儿子的重儿子找出来,然后...,然后找出重儿子的重儿子的重儿子的...的重儿子,将其结成一个链,然后根节点就是该链的链顶。

然后将根节点不是重儿子的儿子作为根节点,重复上两行的操作。

这样树链剖分就完成了。

然后怎么查询&&修改呢。

首先对于链的修改,我们对于一条链(u,v)(其中u的深度比v深即v在u上方,并且每次操作要确保u在v的上方)

如果u,v的top不是同一个

证明u,v不在同一条链上

我们先对深度深的u那条链修改(top[u],u)

然后u重新定义为top[u]的父亲节点,再判断top[u],top[v]的深度

然后继续修改u的那条链

直到top[u]==top[v]

这时我们对(v,u)进行修改即可。

然后询问也是差不多的,这样1,2种操作就处理完了。

然后3,4操作更简单。

我们回顾深搜第二遍,我们发现某个节点的子树的所有编号都是按照顺序来的。

所以我们直接对(id[x],id[x]+size[x]-1)进行修改或询问即可。

最后要注意的就是快读,无向边,%数,还有long long,就没有什么好说的了。

如果你线段树还有问题,请左转 P3372 【模板】线段树1

#include<iostream>
#include<cstdio>
using namespace std;

struct edge{
    long long to,next;
}e[200010];
long long n,m,root,mode,len,tot;
long long a[100010],tree[400010],lazy[400010];
long long head[100010],real[100010],id[100010],fa[100010],hson[100010],dep[100010],size[100010],top[100010];

long long v_in(){//快读 
    long long sum=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}

void add(long long u,long long v){//加边 
    e[++len].to=v;
    e[len].next=head[u];
    head[u]=len;
}

/*线段树(Segment Tree)*/ 

void pushup(long long rt){//上推 
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void pushdown(long long rt,long long ln,long long rn){//下推 
    if (lazy[rt]){
        tree[rt<<1]+=lazy[rt]*ln;
        tree[rt<<1|1]+=lazy[rt]*rn;
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}

void build(long long l,long long r,long long rt){//建树 
    if (l==r){
        tree[rt]=a[real[l]];
        return;
    }
    long long mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}

void update(long long l,long long r,long long rt,long long left,long long right,long long c){//修改操作 
    if (l>=left&&r<=right){
        tree[rt]+=c*(r-l+1);
        lazy[rt]+=c;
        return;
    }
    long long mid=(l+r)>>1;
    pushdown(rt,mid-l+1,r-mid);
    if (mid>=left) update(l,mid,rt<<1,left,right,c);
    if (mid+1<=right) update(mid+1,r,rt<<1|1,left,right,c);
    pushup(rt);
}

long long query(long long l,long long r,long long rt,long long left,long long right){//询问操作 
    if (l>=left&&r<=right){
        return tree[rt]%mode;
    }
    long long mid=(l+r)>>1,ans=0;
    pushdown(rt,mid-l+1,r-mid);
    if (mid>=left) ans=(ans+query(l,mid,rt<<1,left,right))%mode;
    if (mid+1<=right) ans=(ans+query(mid+1,r,rt<<1|1,left,right))%mode;
    pushup(rt);
    return ans;
}

/*树链剖分*/

void dfs1(long long u,long long f){//第一遍深搜(建树,记录fa,size,dep,hson) 
    fa[u]=f;
    size[u]=1;
    for (long long i=head[u];i!=0;i=e[i].next){
        long long v=e[i].to;
        if (fa[u]!=v){
            dep[v]=dep[u]+1;
            dfs1(v,u);
            if (hson[u]==0||size[hson[u]]<size[v]) hson[u]=v;
            size[u]+=size[v];
        }
    }
}

void dfs2(long long u,long long anc){//第二遍深搜(分链,重新编号,记录top,id,real) 
    top[u]=anc;
    id[u]=++tot;
    real[tot]=u;
    if (hson[u]==0) return;
    dfs2(hson[u],anc);
    for (long long i=head[u];i!=0;i=e[i].next){
        long long v=e[i].to;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

void chain_add(){//1操作 
    long long u=v_in(),v=v_in(),w=v_in();
    long long tu=top[u],tv=top[v];
    while (tu!=tv){
        if (dep[tu]<dep[tv]){
            swap(tu,tv);
            swap(u,v);
        }
        update(1,n,1,id[tu],id[u],w);
        u=fa[tu];
        tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    update(1,n,1,id[v],id[u],w);
}

void chain_query(){//2操作 
    long long u=v_in(),v=v_in();
    long long tu=top[u],tv=top[v],ans=0;
    while (tu!=tv){
        if (dep[tu]<dep[tv]){
            swap(tu,tv);
            swap(u,v);
        }
        ans=(ans+query(1,n,1,id[tu],id[u]))%mode;
        u=fa[tu];
        tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    ans=(ans+query(1,n,1,id[v],id[u]))%mode;
    printf("%lld\n",ans);
}

void tree_add(){//3操作 
    long long x=v_in(),w=v_in();
    update(1,n,1,id[x],id[x]+size[x]-1,w);
}

void tree_query(){//4操作 
    long long x=v_in();
    printf("%lld\n",query(1,n,1,id[x],id[x]+size[x]-1)%mode);
}

int main(){
    n=v_in();
    m=v_in();
    root=v_in();
    mode=v_in();
    for (long long i=1;i<=n;i++) a[i]=v_in();
    for (long long i=1;i<n;i++){
        long long u=v_in(),v=v_in();
        add(u,v);//无向边 
        add(v,u);
    }
    dep[root]=1;
    dfs1(root,0);
    dfs2(root,root);
    build(1,n,1);
    for (long long i=1;i<=m;i++){
        long long q=v_in();
        if (q==1) chain_add();
        else if (q==2) chain_query();
        else if (q==3) tree_add();
        else tree_query();
    }
    return 0;
}