Gym 101138J Valentina and the Gift Tree（樹(shù)鏈剖分）
樹(shù)鏈剖分，線段樹(shù)
第一次學(xué)樹(shù)鏈剖分。。就搞了這么難一題。。各種代碼看了好幾天才明白。。
傳送門(mén)：CodeForce
傳送門(mén)：HustOJ
要是想要測(cè)試數(shù)據(jù)和別人的代碼，可以去這個(gè)OJ(不要干壞事哦~) 傳送門(mén)：Hackerearth
題意
建議讀原題。 一棵樹(shù)，100000節(jié)點(diǎn)，樹(shù)上每個(gè)節(jié)點(diǎn)有權(quán)值，整數(shù)。有500000個(gè)查詢(xún)，每次查詢(xún)給樹(shù)上兩點(diǎn)。求樹(shù)上兩點(diǎn)形成的路徑上（包括兩端點(diǎn)），最大連續(xù)子區(qū)間權(quán)值和。 關(guān)于連續(xù)子區(qū)間權(quán)值和，比如第一個(gè)樣例的第一個(gè)查詢(xún)，路徑權(quán)值是2 -1 -2 5。連續(xù)子區(qū)間權(quán)值和是5。
思路
10w節(jié)點(diǎn)，50w查詢(xún)。。肯定要樹(shù)鏈剖分。。關(guān)于最大連續(xù)子區(qū)間權(quán)值和，用線段樹(shù)維護(hù)。
先說(shuō)說(shuō)線段樹(shù)維護(hù)最大子區(qū)間權(quán)值和。 維護(hù)四個(gè)信息，最大前綴，最大后綴，最大子區(qū)間，區(qū)間和。 區(qū)間合并時(shí)，大區(qū)間最大前綴=max（左子最大前綴，左子區(qū)間和+右子最大前綴）。后綴同理。 大區(qū)間最大子區(qū)間=max（左子最大子區(qū)間，右子最大子區(qū)間，左子最大后綴+右子最大前綴）
struct STREE{ //維護(hù)最大前綴，最大后綴，最大子區(qū)間，區(qū)間和 LL MPRefix, MPostfix, Sum, MaxValue; STREE() { MPostfix=MPrefix=Sum=0;MaxValue=-loo; } STREE(LL l, LL r, LL s, LL m) { MPrefix=l;MPostfix=r; Sum=s;MaxValue=m; } STREE Operator + (const STREE &a)const { STREE New; New.MPrefix=max(MPrefix, Sum+a.MPrefix); New.MPostfix=max(a.MPostfix, a.Sum+MPostfix); New.Sum=Sum+a.Sum; New.MaxValue=max(a.MaxValue, max(MaxValue, MPostfix+a.MPrefix)); return New; }}Stree[MAXN<<2];然后是樹(shù)鏈剖分。樹(shù)鏈剖分其實(shí)就是將一棵樹(shù)節(jié)點(diǎn)重新編號(hào)，存到數(shù)據(jù)結(jié)構(gòu)(比如線段樹(shù))里面。 為什么要重新編號(hào)呢？因?yàn)榫€段樹(shù)可以區(qū)間更新、區(qū)間查詢(xún)，而如果不重新給樹(shù)編號(hào)，那么我們無(wú)法最大程度的利用區(qū)間的特性。 剖分后，有重鏈，輕鏈的說(shuō)法。重鏈就是由大部分節(jié)點(diǎn)構(gòu)成的鏈。 我們通過(guò)重新編號(hào)，使得重鏈在線段樹(shù)里面連續(xù)保存，這樣對(duì)樹(shù)更新時(shí)，占了大部分節(jié)點(diǎn)的重鏈就可以區(qū)間更新，而其他輕鏈進(jìn)行單點(diǎn)更新，加快速度。 重新編號(hào)的方法就是DFS，有條件的DFS。
關(guān)于樹(shù)鏈剖分的講解：
整體性的講解：%%% 具體步驟方法：%%% 帶圖的單步操作：%%% 我的理解 第一次DFS時(shí)，獲取的信息有深度，父節(jié)點(diǎn)，子樹(shù)節(jié)點(diǎn)個(gè)數(shù)(SonAmount)，重兒子編號(hào)。
void dfs1(int n)//調(diào)用之前初始化Depth[1]=1{ SonAmount[n]=1; for(int i=0;i<G[n].size();i++) { int to=G[n][i]; if(Depth[to]) continue; Depth[to]=Depth[n]+1; Father[to]=n; dfs1(to); SonAmount[n]+=SonAmount[to]; if(SonAmount[to]>SonAmount[Hson[n]]) Hson[n]=to; //如果to的樹(shù)節(jié)點(diǎn)數(shù)目比目前n的重兒子多 那么to是n的重兒子 } return;}第二次DFS時(shí)獲取的信息有DFS序號(hào)，新序號(hào)下的點(diǎn)權(quán)(邊權(quán))，重鏈鏈?zhǔn)?。注意到每個(gè)節(jié)點(diǎn)時(shí)，先DFS重兒子，這樣如果有一條由許多重兒子構(gòu)成的重鏈，那么他們的dfs序號(hào)一定是連續(xù)的，重鏈頭也就是depth最小的那個(gè)節(jié)點(diǎn)。保證了線段樹(shù)區(qū)間更新。
void dfs2(int n, int prev){ Dfsnum[n]=++dfscount;//dfs序號(hào) 建線段樹(shù)用 TreeValue[dfscount]=Val[n];//為線段樹(shù)保存點(diǎn)權(quán) TopOfHeavyChain[n]=prev;//重鏈頭 if(!Hson[n]) return; dfs2(Hson[n], prev); for(int i=0;i<G[n].size();i++)//dfs輕兒子 { int to=G[n][i]; if(to==Hson[n]||to==Father[n]) continue; dfs2(to, to); }}最后查詢(xún)時(shí)，查詢(xún)兩個(gè)節(jié)點(diǎn)ab，如果不在同一條重鏈上，那么往上跳，跳的方法就是不斷查詢(xún)a到fa=TopOfHeavyChain[a]，以及b和fb=TopOfHeavyChain[b]，a=father[fa]，b=father[fb]，到一條重鏈后最后查詢(xún)一次這條重鏈。就結(jié)束了。詳見(jiàn)代碼，說(shuō)不太清。
代碼
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>#include<stack>#define _ ios_base::sync_with_stdio(0);cin.tie(0);#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int MAXN=100100;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;vector<int> G[MAXN];int Val[MAXN], Hson[MAXN], SonAmount[MAXN], Father[MAXN], Depth[MAXN];int Dfsnum[MAXN], TreeValue[MAXN], TopOfHeavyChain[MAXN];int dfscount;void AddEdge(int from, int to){ G[from].push_back(to); G[to].push_back(from);}void dfs1(int n){ SonAmount[n]=1; for(int i=0;i<G[n].size();i++) { int to=G[n][i]; if(Depth[to]) continue; Depth[to]=Depth[n]+1; Father[to]=n; dfs1(to); SonAmount[n]+=SonAmount[to]; if(SonAmount[to]>SonAmount[Hson[n]]) Hson[n]=to; //如果to的樹(shù)節(jié)點(diǎn)數(shù)目比目前n的重兒子多 那么to是n的重兒子 } return;}void dfs2(int n, int prev){ Dfsnum[n]=++dfscount;//dfs序號(hào) 建線段樹(shù)用 TreeValue[dfscount]=Val[n];//為線段樹(shù)保存點(diǎn)權(quán) TopOfHeavyChain[n]=prev;//重鏈頭 if(!Hson[n]) return; dfs2(Hson[n], prev); for(int i=0;i<G[n].size();i++) { int to=G[n][i]; if(to==Hson[n]||to==Father[n]) continue; dfs2(to, to); }}struct STREE{ LL MPrefix, MPostfix, Sum, MaxValue; //STREE(LL x) { MPostfix=MPrefix=Sum=MaxValue=x; } STREE() { MPostfix=MPrefix=Sum=0;MaxValue=-loo; } STREE(LL l, LL r, LL s, LL m) { MPrefix=l;MPostfix=r; Sum=s;MaxValue=m; } STREE operator + (const STREE &a)const { STREE New; New.MPrefix=max(MPrefix, Sum+a.MPrefix); New.MPostfix=max(a.MPostfix, a.Sum+MPostfix); New.Sum=Sum+a.Sum; New.MaxValue=max(a.MaxValue, max(MaxValue, MPostfix+a.MPrefix)); return New; }}Stree[MAXN<<2];void build(int l, int r, int rt){ if(l==r) { Stree[rt].MaxValue=Stree[rt].MPostfix=Stree[rt].MPrefix=Stree[rt].Sum=TreeValue[l]; return; } int m=(l+r)>>1; build(lson); build(rson); Stree[rt]=Stree[rt<<1]+Stree[rt<<1|1]; return;}STREE query(int L, int R, int l, int r, int rt){ if(L<=l&&r<=R) return Stree[rt]; int m=(l+r)>>1; if(m< L) return query(L, R, rson); if(m>=R) return query(L, R, lson); return (query(L, R, lson)+query(L, R, rson));}LL solve(int a, int b,int n){ STREE lc, rc; int fa=TopOfHeavyChain[a], fb=TopOfHeavyChain[b]; while(fa!=fb) { if(Depth[fa]>Depth[fb]) { lc=query(Dfsnum[fa], Dfsnum[a], 1, n, 1)+lc; a=Father[fa]; fa=TopOfHeavyChain[a]; } else { rc=query(Dfsnum[fb], Dfsnum[b], 1, n, 1)+rc; b=Father[fb]; fb=TopOfHeavyChain[b]; } } if(Depth[a]>Depth[b]) { lc=query(Dfsnum[b], Dfsnum[a], 1, n, 1)+lc; } else { rc=query(Dfsnum[a], Dfsnum[b], 1, n, 1)+rc; } swap(lc.MPostfix, lc.MPrefix); return ((lc+rc).MaxValue);}int main(){ _ int n;cin>>n; for(int i=1;i<n;i++) { int ta, tb; cin>>ta>>tb; AddEdge(ta, tb); } for(int i=1;i<=n;i++) cin>>Val[i]; Depth[1]=1;dfs1(1);dfs2(1, 1); build(1, n, 1); int m; cin>>m; while(m--) { int ta, tb; cin>>ta>>tb; cout<<solve(ta, tb, n)<<endl; } //system("pause"); return 0;}
