題目描述
如題，已知一棵包含N個結點的樹（連通且無環(huán)），每個節(jié)點上包含一個數(shù)值，需要支持以下操作：

操作1： 格式： 1 x y z 表示將樹從x到y(tǒng)結點最短路徑上所有節(jié)點的值都加上z

操作2： 格式： 2 x y 表示求樹從x到y(tǒng)結點最短路徑上所有節(jié)點的值之和

操作3： 格式： 3 x z 表示將以x為根節(jié)點的子樹內所有節(jié)點值都加上z

操作4： 格式： 4 x 表示求以x為根節(jié)點的子樹內所有節(jié)點值之和

輸入輸出格式
輸入格式：
第一行包含4個正整數(shù)N、M、R、P，分別表示樹的結點個數(shù)、操作個數(shù)、根節(jié)點序號和取模數(shù)（即所有的輸出結果均對此取模）。

接下來一行包含N個非負整數(shù)，分別依次表示各個節(jié)點上初始的數(shù)值。

接下來N-1行每行包含兩個整數(shù)x、y，表示點x和點y之間連有一條邊（保證無環(huán)且連通）

接下來M行每行包含若干個正整數(shù)，每行表示一個操作，格式如下：

操作1： 1 x y z

操作2： 2 x y

操作3： 3 x z

操作4： 4 x

輸出格式：
輸出包含若干行，分別依次表示每個操作2或操作4所得的結果（對P取模）

輸入輸出樣例
輸入樣例#1：
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
輸出樣例#1：
2
21
說明
時空限制：1s，128M

數(shù)據(jù)規(guī)模：

對于30%的數(shù)據(jù)： N \leq 10, M \leq 10 N≤10,M≤10
對于70%的數(shù)據(jù)： N \leq {10}^3, M \leq {10}^3 N≤10
3
,M≤10
3

對于100%的數(shù)據(jù)： N \leq {10}^5, M \leq {10}^5 N≤10
5
,M≤10
5

（ 其實，純隨機生成的樹LCA+暴力是能過的，可是，你覺得可能是純隨機的么233 ）

樣例說明：

樹的結構如下：

各個操作如下：

故輸出應依次為2、21(重要的事情說三遍：記得取模)
搞了一下午的樹鏈剖分，可算是寫出來個東西。學習樹鏈剖分應該先掌握線段樹，dfs序。否則學起來會很困難。
代碼總之很長，而且之前都是分開寫線段樹，dfs之類的，這一次綜合起來還是有點困難的。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<queue> #define ll long long using namespace std;const int maxx=1e5+100; int fa[maxx],son[maxx],dep[maxx]; int pre[maxx],id[maxx],top[maxx]; int size[maxx],a[maxx],head[maxx]; int n,m,root,mod,sign; int tot; struct edge{int to;int next; }e[maxx*2]; struct node{int l;int r;int v;int lazy; }p[maxx*4]; /*-----------事前準備---------*/ int inn() { char ch; int a=0; while((ch=getchar())==' '||ch=='\n'); a+=ch-'0'; while((ch=getchar())!=' '&&ch!='\n') { a*=10; a+=ch-'0'; } return a; } void init() {tot=0;sign=0;memset(dep,0,sizeof(dep));memset(size,0,sizeof(size));memset(head,0,sizeof(head)); } void addedge(int x,int y) {e[++tot].next=head[x];e[tot].to=y;head[x]=tot; } /*----------------dfs---------------*/ void dfs1(int u,int f) {size[u]=1;dep[u]=dep[fa[u]]+1;for(int i=head[u];i;i=e[i].next){int to=e[i].to;if(to==f) continue;//dep[to]=dep[u]+1;fa[to]=u;dfs1(to,u);size[u]+=size[to];if(size[to]>size[son[u]]) son[u]=to;} } void dfs2(int u,int Top) {top[u]=Top;id[u]=++sign;pre[sign]=u;if(son[u]) dfs2(son[u],Top);for(int i=head[u];i;i=e[i].next){int to=e[i].to;if(to!=fa[u]&&to!=son[u])dfs2(to,to);} } /*-------------線段樹-------------*/ void pushup(int cur) {p[cur].v=(p[2*cur].v+p[2*cur+1].v)%mod; } void pushdown(int cur) {if(p[cur].lazy){p[2*cur].lazy=(p[cur].lazy+p[cur*2].lazy)%mod;p[2*cur+1].lazy=(p[cur].lazy+p[2*cur+1].lazy)%mod;p[2*cur].v=(p[2*cur].v+(p[2*cur].r-p[2*cur].l+1)*p[cur].lazy)%mod;p[2*cur+1].v=(p[2*cur+1].v+(p[2*cur+1].r-p[2*cur+1].l+1)*p[cur].lazy)%mod;p[cur].lazy=0;} } void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].lazy=0;if(l==r){p[cur].v=a[pre[l]];return;}int mid=(l+r)/2;build(l,mid,2*cur);build(mid+1,r,2*cur+1);pushup(cur); } void update(int l,int r,int cur,int add) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r){p[cur].v=(p[cur].v+(p[cur].r-p[cur].l+1)*add%mod)%mod;p[cur].lazy=(p[cur].lazy+add)%mod;return ;}pushdown(cur);int mid=(L+R)/2;if(r<=mid) update(l,r,2*cur,add);else if(l>mid) update(l,r,2*cur+1,add);else {update(l,mid,2*cur,add);update(mid+1,r,2*cur+1,add);}pushup(cur); } int query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r){return p[cur].v%mod;}pushdown(cur);int mid=(L+R)/2;if(r<=mid) return query(l,r,2*cur)%mod;else if(l>mid) return query(l,r,2*cur+1)%mod;else return (query(l,mid,2*cur)+query(mid+1,r,2*cur+1))%mod; } /*--------------樹鏈剖分-------------*/ int Query(int x,int y) {int ret=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);(ret+=query(id[top[x]],id[x],1))%=mod;x=fa[top[x]];}if(id[x]>id[y]) swap(x,y);return (ret+query(id[x],id[y],1))%mod; } void Update(int x,int y,int z) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);update(id[top[x]],id[x],1,z);x=fa[top[x]];}if(id[x]>id[y]) swap(x,y);update(id[x],id[y],1,z); } /*-----------主函數(shù)-----------*/ int main() {while(scanf("%d%d%d%d",&n,&m,&root,&mod)!=EOF){init(); for(int i=1;i<=n;i++) a[i]=inn();int x,y;for(int i=1;i<n;i++){x=inn();y=inn();addedge(x,y);addedge(y,x);}dep[root]=1;dfs1(root,0);dfs2(root,root);build(1,n,1);int k,z;while(m--){k=inn();if(k==1){x=inn();y=inn();z=inn();Update(x,y,z);}else if(k==2){x=inn();y=inn();printf("%d\n",Query(x,y));}else if(k==3){x=inn();y=inn();update(id[x],id[x]+size[x]-1,1,y);}else if(k==4){x=inn();printf("%d\n",query(id[x],id[x]+size[x]-1,1));}}return 0;} }

數(shù)據(jù)結構一般代碼量很多，所以一定不能心浮氣躁。而且要多敲，這樣才能少出錯誤
努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的洛谷3384（树链剖分模板题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。