1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=1e5+5; 4 //要開long long！ 5 #define LL long long 6 vector<int> nei[MAXN]; 7 struct Tedge 8 { 9 int u,v; 10 LL cost; 11 void init() 12 { 13 u=v=cost=0; 14 } 15 } edge[MAXN]; //邊信息 16 struct Node 17 { 18 int l,r; 19 LL sum,lazy; 20 void init() 21 { 22 l=r=0; 23 sum=lazy=0; 24 } 25 } tree[4*MAXN]; //線段樹 26 int newid[MAXN]; //剖分后在線段樹中的編號 27 int newarr[MAXN]; //剖分后產生的新數(shù)組 28 int cnt,top[MAXN]; //cnt為時間戳，top為每個節(jié)點所在重鏈中深度最淺的節(jié)點編號 29 int par[MAXN]; //每個節(jié)點的父節(jié)點 30 int size[MAXN]; //以x節(jié)點為根節(jié)點的子樹的節(jié)點數(shù)量 31 int eid[MAXN]; //par[x]---->x的邊的cost 32 int dep[MAXN]; //每個節(jié)點的深度 33 void dfs(const int &v,const int &pa,const int &ndep) //遍歷樹，找出每個節(jié)點深度、父節(jié)點、size 34 { 35 dep[v]=ndep; 36 par[v]=pa; 37 size[v]=1; 38 for(int i=0;i<nei[v].size();i++) 39 { 40 int u=nei[v][i]; 41 if(u==pa) continue; 42 dfs(u,v,ndep+1); 43 size[v]+=size[u]; 44 } 45 } 46 47 void makeHardPath(const int &v,const int &pa,const int &to) //遍歷樹，找出重鏈 48 { 49 int cho,masiz=0; 50 newarr[cnt]=v; 51 top[v]=to; 52 newid[v]=cnt++; 53 for(int i=0;i<nei[v].size();i++) 54 { 55 int u=nei[v][i]; 56 if(u==pa) continue; 57 if(size[u]>masiz) 58 { 59 masiz=size[u]; 60 cho=u; 61 } 62 } 63 if(!masiz) return; 64 makeHardPath(cho,v,to); 65 for(int i=0;i<nei[v].size();i++) 66 { 67 int u=nei[v][i]; 68 if(u==pa||u==cho) continue; 69 makeHardPath(u,v,u); 70 } 71 } 72 void buildtree(const int &i,const int &l,const int &r) //建線段樹 73 { 74 tree[i].l=l;tree[i].r=r; 75 if(l==r) 76 { 77 tree[i].sum=eid[newarr[l]]; 78 } 79 else 80 { 81 int mid=(l+r)>>1; 82 buildtree(i<<1,l,mid); 83 buildtree((i<<1)|1,mid+1,r); 84 tree[i].sum=tree[i<<1].sum+tree[(i<<1)|1].sum; 85 } 86 } 87 inline void pushdown(const int &i) //下推標記 88 { 89 if(!tree[i].lazy) return; 90 tree[i<<1].lazy+=tree[i].lazy; 91 tree[i<<1|1].lazy+=tree[i].lazy; 92 tree[i<<1].sum+=(tree[i].lazy)*(tree[i<<1].r-tree[i<<1].l+1ll); 93 tree[i<<1|1].sum+=(tree[i].lazy)*(tree[i<<1|1].r-tree[i<<1|1].l+1ll); 94 tree[i].lazy=0; 95 } 96 inline void treeupdate(const int &i,const int &l,const int &r,const LL &z) //區(qū)間更新 97 { 98 if(r<tree[i].l||tree[i].r<l) return; 99 if(tree[i].l>=l&&tree[i].r<=r) 100 { 101 tree[i].sum+=(tree[i].r-tree[i].l+1ll)*z; 102 tree[i].lazy+=z; 103 return; 104 } 105 else 106 { 107 //108行與112行中選一種寫法（當然選108行） 108 pushdown(i); 109 treeupdate(i<<1,l,r,z); 110 treeupdate((i<<1)|1,l,r,z); 111 tree[i].sum=tree[i<<1].sum+tree[(i<<1)|1].sum; 112 // tree[i].sum+=(tree[i].r-tree[i].l+1ll)*tree[i].lazy; 113 } 114 } 115 116 inline LL query(const int &i,const int &l,const int &r) //查詢 117 { 118 if(r<tree[i].l||tree[i].r<l) return 0; 119 if(tree[i].l>=l&&tree[i].r<=r) 120 { 121 return tree[i].sum; 122 } 123 else 124 { 125 pushdown(i); 126 LL res=0; 127 res+=query(i<<1,l,r); 128 res+=query((i<<1)|1,l,r); 129 return res; 130 } 131 } 132 inline LL QUE(int x,int y) 133 { 134 LL res=0; 135 while(top[x]!=top[y]) 136 { 137 if(dep[top[x]]<dep[top[y]]) swap(x,y); 138 res+=query(1,newid[top[x]],newid[x]); 139 x=par[top[x]]; 140 } 141 if(x!=y) 142 { 143 if(dep[x]<dep[y]) swap(x,y); 144 res+=query(1,newid[y]+1,newid[x]); 145 } 146 return res; 147 } 148 inline void ADD(int x,int y,int z) 149 { 150 while(top[x]!=top[y]) 151 { 152 if(dep[top[x]]<dep[top[y]]) swap(x,y); 153 treeupdate(1,newid[top[x]],newid[x],z); 154 x=par[top[x]]; 155 } 156 if(x!=y) 157 { 158 if(dep[x]<dep[y]) swap(x,y); 159 treeupdate(1,newid[y]+1,newid[x],z); 160 } 161 } 162 void init() 163 { 164 memset(par,0,sizeof par); 165 memset(size,0,sizeof size); 166 memset(eid,0,sizeof eid); 167 memset(dep,0,sizeof dep); 168 memset(newid,0,sizeof newid); 169 memset(top,0,sizeof top); 170 cnt=1; 171 for(int i=0;i<4*MAXN;i++) tree[i].init(); 172 for(int i=0;i<MAXN;i++) 173 { 174 nei[i].clear(); 175 edge[i].init(); 176 } 177 } 178 int main() 179 { 180 int T; 181 scanf("%d",&T); 182 while(T--) 183 { 184 init(); 185 int n,m; 186 scanf("%d %d",&n,&m); 187 for(int i=0;i<n-1;i++) 188 { 189 scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].cost); 190 nei[edge[i].u].push_back(edge[i].v); 191 nei[edge[i].v].push_back(edge[i].u); 192 } 193 dfs(1,1,0); 194 for(int i=0;i<n-1;i++) 195 { 196 if(par[edge[i].v]==edge[i].u) 197 { 198 eid[edge[i].v]=edge[i].cost; 199 } 200 else 201 { 202 eid[edge[i].u]=edge[i].cost; 203 } 204 } 205 makeHardPath(1,1,1); 206 buildtree(1,1,n); 207 while(m--) 208 { 209 char s[10]; 210 scanf("%s",s); 211 int x,y; 212 scanf("%d %d",&x,&y); 213 LL w; 214 if(s[0]=='Q') 215 { 216 printf("%lld\n",QUE(x,y)); 217 } 218 else 219 { 220 scanf("%lld",&w); 221 ADD(x,y,w); 222 } 223 } 224 } 225 return 0; 226 }

?

轉載于:https://www.cnblogs.com/unnamed05/p/9300333.html

總結

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

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