題目描述

如題，已知一棵包含N個結點的樹（連通且無環），每個節點上包含一個數值，需要支持以下操作：

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

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

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

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

輸入輸出格式

輸入格式：

?

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

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

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

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

操作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

數據規模：

對于30%的數據：N<=10，M<=10

對于70%的數據：N<=1000，M<=1000

對于100%的數據：N<=100000，M<=100000

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

樣例說明：

樹的結構如下：

各個操作如下：

故輸出應依次為2、21(重要的事情說三遍：記得取模)

一些

有關樹鏈剖分：

?首先，要會建樹，建議用鏈表（我一開始各種T，而后抄的shenben學長的），指針，stl等。（不爆空間就好）

一些概念：

樹鏈剖分實際上就是把樹按一種特定規則拆解成一條又一條的鏈。

這些鏈經過所有的點，稱為重鏈，鏈上的邊，為重邊，其余（一般很少）的邊為輕邊。

size：以該節點為根節點構建的樹上的節點數；

重兒子：某一節點所有兒子中size值最大的一個，由重邊與該節點相連，不可能位于鏈首；

輕兒子：不是宗子（重兒子）的兒子，成為新的諸侯王|族長（新鏈的鏈首節點）；

如下圖：

同一枝上一個色的屬于同一條重鏈。

步驟：

讀入數據：

讀入點（p）權（k）；

讀入邊并存放在鏈表中；

恩，我不會。

Dfs1：

求出點（p）的父節點（f），深度（p），size（sz），重兒子（ws）；

Dfs2：

求出點（p）的線段坐標（p），鏈首節點（t），鏈尾節點（w）；

build：

建造線段樹；

處理處置：

1&2：lca；

3&4：從 根節點的線段坐標（p[].p） 到 根節點的線段坐標+根節點的size-1（p[].p+p[].sz-1）就是了。（可以想象）

return 0；

有關變量的一些說明： n節點，m操作，root根節點，mod模數；a，b，c，d，ans輔助變量；node{//點對應 k權值，f父節點，d深度；
sz：size ws重兒子； p點對于線段上的位置坐標； t點所在鏈鏈首節點； }p[1*]s[]線段暫存重鏈節點； l線段長； nl線段讀入線段樹時使用；tree{l,r,s,flag;}t[4*]//基本線段樹（然而我一直開的2*，CE Qrz） h[]記錄點對應鏈表上的啟示位置hs表示鏈表存到第幾個了； nate{//應該是鏈表，抄的shenben學長的東西（原為node） s連接到的節點； n下一個（原為next） }p[2*]

代碼實現：

1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,m,l,hs,nl,lfs,root,mod; 5 int a,b,c,d,ans; 6 int s[100010],h[100010]; 7 struct node 8 { 9 int k,f,d,sz; 10 int ws; 11 int p,t,w; 12 }p[100010]; 13 struct edge{int s,n;}e[200010]; 14 struct tree{int l,r,s,flag;}t[400010]; 15 void heritage(int k) 16 { 17 int ls=k*2,rs=k*2+1; 18 t[ls].flag=(t[ls].flag+t[k].flag)%mod; 19 t[ls].s+=(t[ls].r-t[ls].l+1)*t[k].flag%mod; 20 t[rs].flag=(t[rs].flag+t[k].flag)%mod; 21 t[rs].s+=(t[rs].r-t[rs].l+1)*t[k].flag%mod; 22 t[k].flag=0; 23 } 24 void build(int k,int l,int r) 25 { 26 int ls=k*2,rs=k*2+1; 27 t[k].l=l;t[k].r=r; 28 if(l==r) 29 { 30 t[k].s=s[++nl]; 31 return; 32 } 33 int mid=(l+r)/2; 34 build(ls,l,mid); 35 build(rs,mid+1,r); 36 t[k].s=t[ls].s+t[rs].s; 37 } 38 void change(int k,int l,int r,int v) 39 { 40 int ls=k*2,rs=k*2+1; 41 if(t[k].l==l&&t[k].r==r) 42 { 43 t[k].flag=(t[k].flag+v)%mod; 44 t[k].s+=(t[k].r-t[k].l+1)*v%mod; 45 return; 46 } 47 if(t[k].flag) heritage(k); 48 int mid=(t[k].l+t[k].r)/2; 49 if( l <= mid ) 50 change(ls,l,min(r,mid),v); 51 if( r > mid ) 52 change(rs,max(l,mid+1),r,v); 53 t[k].s=(t[ls].s+t[rs].s)%mod; 54 } 55 int query(int k,int l,int r) 56 { 57 int ls=k*2,rs=k*2+1; 58 if(t[k].l==l&&t[k].r==r) return t[k].s; 59 if(t[k].flag) heritage(k); 60 int mid=(t[k].l+t[k].r)/2,ans=0; 61 if( l <= mid ) 62 ans+=query(ls,l,min(r,mid))%mod; 63 if( r > mid ) 64 ans+=query(rs,max(l,mid+1),r)%mod; 65 return ans%mod; 66 } 67 bool traceability(int x,int y) 68 { 69 if(x==p[y].w) return 0; 70 while(p[x].d>=p[y].d) 71 { 72 if(p[x].t==p[y].t) return 1; 73 x=p[p[x].t].f; 74 } 75 } 76 inline void add(int x,int y){e[++hs]=(edge){y,h[x]};h[x]=hs;} 77 void dfs1(int k,int f,int d) 78 { 79 p[k].f=f; 80 p[k].d=d; 81 p[k].sz=1; 82 for(int i=h[k];i;i=e[i].n) 83 { 84 if(e[i].s!=f) 85 { 86 dfs1(e[i].s,k,d+1); 87 p[k].sz+=p[e[i].s].sz; 88 if(p[e[i].s].sz>p[p[k].ws].sz) 89 p[k].ws=e[i].s; 90 } 91 } 92 } 93 void dfs2(int k) 94 { 95 s[++l]=p[k].k; 96 p[k].p=l; 97 if(p[k].ws) 98 { 99 p[p[k].ws].t=p[k].t; 100 dfs2(p[k].ws); 101 p[k].w=p[k].ws; 102 } 103 for(int i=h[k];i;i=e[i].n) 104 if(e[i].s!=p[k].ws&&e[i].s!=p[k].f) 105 { 106 p[e[i].s].w=p[e[i].s].t=e[i].s; 107 dfs2(e[i].s); 108 } 109 } 110 int main() 111 { 112 scanf("%d%d%d%d",&n,&m,&root,&mod); 113 for(int i=1;i<=n;i++) scanf("%d",&p[i].k); 114 for(int i=1;i<n;i++) 115 { 116 scanf("%d%d",&a,&b); 117 add(a,b);add(b,a); 118 } 119 dfs1(root,root,1); 120 p[root].w=p[root].t=root; 121 dfs2(root); 122 build(1,1,l); 123 while(m--) 124 { 125 scanf("%d",&a); 126 if(a==1) 127 { 128 scanf("%d%d%d",&b,&c,&d); 129 d%=mod; 130 for(;p[b].t!=p[c].t;b=p[p[b].t].f) 131 { 132 if(p[p[b].t].d<p[p[c].t].d) swap(b,c); 133 change(1,p[p[b].t].p,p[b].p,d); 134 } 135 if(p[b].d>p[c].d) swap(b,c); 136 change(1,p[b].p,p[c].p,d); 137 } 138 if(a==2) 139 { 140 scanf("%d%d",&b,&c); 141 ans=0; 142 for(;p[b].t!=p[c].t;b=p[p[b].t].f) 143 { 144 if(p[p[b].t].d<p[p[c].t].d) swap(b,c); 145 ans+=query(1,p[p[b].t].p,p[b].p); 146 ans%=mod; 147 } 148 if(p[b].d>p[c].d) swap(b,c); 149 ans+=query(1,p[b].p,p[c].p); 150 ans%=mod; 151 printf("%d\n",ans); 152 } 153 if(a==3) 154 { 155 scanf("%d%d",&b,&c); 156 c%=mod; 157 change(1,p[b].p,p[b].p+p[b].sz-1,c); 158 } 159 if(a==4) 160 { 161 scanf("%d",&b); 162 ans=0; 163 ans=query(1,p[b].p,p[b].p+p[b].sz-1)%mod; 164 printf("%d\n",ans); 165 } 166 } 167 return 0; 168 }

我記得我上次代碼過百行是在201...

1 #include<cstdio> 2 #include<iostream> 3 #define ls k*2 4 #define rs k*2+1 5 using namespace std; 6 int n,m,l,hs,nl,lfs,root,mod; 7 int a,b,c,d,ans; 8 int s[100010],h[100010]; 9 struct node{int k,f,d,sz,ws,p,t;}p[100010]; 10 struct nate{int s,n;}e[200010]; 11 struct tree{int l,r,s,f;}t[400010]; 12 void heritage(int k){ 13 t[ls].f=(t[ls].f+t[k].f)%mod; 14 t[ls].s+=(t[ls].r-t[ls].l+1)*t[k].f%mod; 15 t[rs].f=(t[rs].f+t[k].f)%mod; 16 t[rs].s+=(t[rs].r-t[rs].l+1)*t[k].f%mod; 17 t[k].f=0; 18 } 19 void build(int k,int l,int r){ 20 t[k].l=l;t[k].r=r; 21 if(l==r){t[k].s=s[++nl];return;} 22 int mid=(l+r)/2; 23 build(ls,l,mid); 24 build(rs,mid+1,r); 25 t[k].s=t[ls].s+t[rs].s; 26 } 27 void change(int k,int l,int r,int v){ 28 if(t[k].l==l&&t[k].r==r){ 29 t[k].f=(t[k].f+v)%mod; 30 t[k].s+=(t[k].r-t[k].l+1)*v%mod; 31 return; 32 } 33 if(t[k].f) heritage(k); 34 int mid=(t[k].l+t[k].r)/2; 35 if(l<=mid) change(ls,l,min(r,mid),v); 36 if(r>mid) change(rs,max(l,mid+1),r,v); 37 t[k].s=(t[ls].s+t[rs].s)%mod; 38 } 39 int query(int k,int l,int r){ 40 if(t[k].l==l&&t[k].r==r) return t[k].s; 41 if(t[k].f) heritage(k); 42 int mid=(t[k].l+t[k].r)/2,ans=0; 43 if(l<=mid) ans+=query(ls,l,min(r,mid))%mod; 44 if(r>mid) ans+=query(rs,max(l,mid+1),r)%mod; 45 return ans%mod; 46 } 47 inline void add(int x,int y){e[++hs]=(nate){y,h[x]};h[x]=hs;} 48 void dfs1(int k,int f,int d){ 49 p[k].f=f;p[k].d=d;p[k].sz=1; 50 for(int i=h[k];i;i=e[i].n) 51 if(e[i].s!=f){ 52 dfs1(e[i].s,k,d+1); 53 p[k].sz+=p[e[i].s].sz; 54 if(p[e[i].s].sz>p[p[k].ws].sz) p[k].ws=e[i].s; 55 } 56 } 57 void dfs2(int k){ 58 s[++l]=p[k].k;p[k].p=l; 59 if(p[k].ws){ 60 p[p[k].ws].t=p[k].t; 61 dfs2(p[k].ws); 62 } 63 for(int i=h[k];i;i=e[i].n) 64 if(e[i].s!=p[k].ws&&e[i].s!=p[k].f){ 65 p[e[i].s].t=e[i].s; 66 dfs2(e[i].s); 67 } 68 } 69 int main(){ 70 scanf("%d%d%d%d",&n,&m,&root,&mod); 71 for(int i=1;i<=n;i++) scanf("%d",&p[i].k); 72 for(int i=1;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a); 73 dfs1(root,root,1); 74 dfs2(root); 75 build(1,1,l); 76 while(m--){ 77 scanf("%d",&a); 78 if(a==1){ 79 scanf("%d%d%d",&b,&c,&d);d%=mod; 80 for(;p[b].t!=p[c].t;b=p[p[b].t].f){ 81 if(p[p[b].t].d<p[p[c].t].d) swap(b,c); 82 change(1,p[p[b].t].p,p[b].p,d); 83 } 84 if(p[b].d>p[c].d) swap(b,c); 85 change(1,p[b].p,p[c].p,d); 86 } 87 if(a==2){ 88 scanf("%d%d",&b,&c);ans=0; 89 for(;p[b].t!=p[c].t;b=p[p[b].t].f){ 90 if(p[p[b].t].d<p[p[c].t].d) swap(b,c); 91 ans+=query(1,p[p[b].t].p,p[b].p),ans%=mod; 92 } 93 if(p[b].d>p[c].d) swap(b,c); 94 ans+=query(1,p[b].p,p[c].p),ans%=mod; 95 printf("%d\n",ans); 96 } 97 if(a==3){ 98 scanf("%d%d",&b,&c),c%=mod; 99 change(1,p[b].p,p[b].p+p[b].sz-1,c); 100 } 101 if(a==4){ 102 scanf("%d",&b),ans=0; 103 ans=query(1,p[b].p,p[b].p+p[b].sz-1)%mod; 104 printf("%d\n",ans); 105 } 106 } 107 return 0; 108 } 無注釋版（我不是邪教徒）（反復更新）

評測結果：

搞了一天半，身心俱疲啊~

題目來源：洛谷

轉載于:https://www.cnblogs.com/J-william/p/6379883.html

總結

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

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