题目大意：树链剖分，有4个操作，1：把x->y路径上值都加上z，2：求x->y路径上值之和，3：把x的子树值都加上z，4：求x的子树值之和

题解：树链剖分，就是对一棵树分成几条链，把树形变为线性，减少处理难度

具体每个函数的作用见程序

 

C++ Code：

#include
     
      using namespace std;const int maxn=100100;int n,m,r,value[maxn],value_temp[maxn];long long mod;int idx;int dfn[maxn],fa[maxn],dep[maxn];int top[maxn],siz[maxn],son[maxn];int head[maxn],cnt;long long ts[101000<<2],cover[101000<<2];void swap(int &a,int &b){a^=b^=a^=b;}struct Edge{	int to,nxt;}e[maxn<<1];void addE(int a,int b){//前向星	e[++cnt]=(Edge){b,head[a]};	head[a]=cnt;}void pushdown(int rt,int len){//线段树lazy_tag的pushdown	cover[rt<<1]=(cover[rt<<1]+cover[rt])%mod;	cover[rt<<1|1]=(cover[rt<<1|1]+cover[rt])%mod;	ts[rt<<1]=(ts[rt<<1]+cover[rt]*(len+1>>1))%mod;	ts[rt<<1|1]=(ts[rt<<1|1]+cover[rt]*(len>>1))%mod;	cover[rt]=0;}void add(int rt,int l,int r,int L,int R,long long z){//线段树区间加	if (L<=l&&R>=r){		ts[rt]=(ts[rt]+z*(r-l+1))%mod;		cover[rt]+=z;		return;	}	if (cover[rt])pushdown(rt,r-l+1);	int mid=l+r>>1;	if (L<=mid)add(rt<<1,l,mid,L,R,z);	if (R>mid)add(rt<<1|1,mid+1,r,L,R,z);	ts[rt]=(ts[rt<<1]+ts[rt<<1|1])%mod;}long long ask(int rt,int l,int r,int L,int R){//线段数询问区间	if (L<=l&&R>=r)return ts[rt];	if (cover[rt])pushdown(rt,r-l+1);	long long res=0;	int mid=l+r>>1;	if (L<=mid)res+=ask(rt<<1,l,mid,L,R);	if (R>mid)res+=ask(rt<<1|1,mid+1,r,L,R);	return res%mod;}void build(int rt,int l,int r){//线段树建树    if (l==r){        ts[rt]=value[l];        return;    }    int mid=l+r>>1;    build(rt<<1,l,mid);    build(rt<<1|1,mid+1,r);    ts[rt]=(ts[rt<<1]+ts[rt<<1|1])%mod;}void dfs1(int rt){//树链剖分，求出每个节点的子树大小，其父亲，深度和重儿子（在它儿子中子树大小最大的）	siz[rt]=1;	for (int i=head[rt];i;i=e[i].nxt){		int ne=e[i].to;		if (ne!=fa[rt]){			fa[ne]=rt;			dep[ne]=dep[rt]+1;			dfs1(ne);			if (son[rt]==0||siz[ne]>siz[son[rt]])son[rt]=ne;			siz[rt]+=siz[ne];		}	}}void dfs2(int rt){/*树链剖分，求出每个节点的新编号（dfn，先重儿子再轻儿子，保证重链编号连续，又因为是深搜，保证了每棵子树编号连续），以及每个节点处在的重链的编号（即最上面一个节点的编号）*/	dfn[rt]=++idx;	int ne=son[rt];	if (ne)top[ne]=top[rt],dfs2(ne);	for (int i=head[rt];i;i=e[i].nxt){		ne=e[i].to;		if (ne==son[rt]||ne==fa[rt])continue;		top[ne]=ne;		dfs2(ne);	}}void add_E(int x,int y,long long z){/*操作1，因为每个点有了新编号，而且重链编号是连续的，所以可以每次把x，y中所在编号位置深的一条重链加上z（用线段树），然后把这个编号跳到重链顶端的父节点，然后重复该操作，直到x和y在同一条重链上，处理这两个节点之间的节点（还是线段树）*/	while (top[x]!=top[y]){		if (dep[top[x]]
      
       dep[y])swap(x,y);	add(1,1,n,dfn[x],dfn[y],z);}long long ask_E(int x,int y){//操作2，类似操作1，就是把加变成了询问	long long res=0;	while (top[x]!=top[y]){		if (dep[top[x]]
       
        dep[y])swap(x,y);	res=(res+ask(1,1,n,dfn[x],dfn[y]))%mod;	return res;}void add_T(int x,long long z) {//操作3，因为子树编号连续，所以直接更改	add(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);}long long ask_T(int x) {//操作4，因为子树编号连续，所以直接更改	return ask(1,1,n,dfn[x],dfn[x]+siz[x]-1);}int main(){	scanf("%d%d%d%lld",&n,&m,&r,&mod);	for (int i=1;i<=n;i++)scanf("%d",&value_temp[i]);	for (int i=1;i