Gym 101138J Valentina and the Gift Tree（樹鏈剖分）
樹鏈剖分，線段樹
第一次學樹鏈剖分。。就搞了這么難一題。。各種代碼看了好幾天才明白。。
傳送門：CodeForce
傳送門：HustOJ
要是想要測試數據和別人的代碼，可以去這個OJ(不要干壞事哦~) 傳送門：Hackerearth
題意
建議讀原題。 一棵樹，100000節點，樹上每個節點有權值，整數。有500000個查詢，每次查詢給樹上兩點。求樹上兩點形成的路徑上（包括兩端點），最大連續子區間權值和。 關于連續子區間權值和，比如第一個樣例的第一個查詢，路徑權值是2 -1 -2 5。連續子區間權值和是5。
思路
10w節點，50w查詢。?？隙ㄒ獦滏溒史帧?。關于最大連續子區間權值和，用線段樹維護。
先說說線段樹維護最大子區間權值和。 維護四個信息，最大前綴，最大后綴，最大子區間，區間和。 區間合并時，大區間最大前綴=max（左子最大前綴，左子區間和+右子最大前綴）。后綴同理。 大區間最大子區間=max（左子最大子區間，右子最大子區間，左子最大后綴+右子最大前綴）
struct STREE{ //維護最大前綴，最大后綴，最大子區間，區間和 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];然后是樹鏈剖分。樹鏈剖分其實就是將一棵樹節點重新編號，存到數據結構(比如線段樹)里面。 為什么要重新編號呢？因為線段樹可以區間更新、區間查詢，而如果不重新給樹編號，那么我們無法最大程度的利用區間的特性。 剖分后，有重鏈，輕鏈的說法。重鏈就是由大部分節點構成的鏈。 我們通過重新編號，使得重鏈在線段樹里面連續保存，這樣對樹更新時，占了大部分節點的重鏈就可以區間更新，而其他輕鏈進行單點更新，加快速度。 重新編號的方法就是DFS，有條件的DFS。
關于樹鏈剖分的講解：
整體性的講解：%%% 具體步驟方法：%%% 帶圖的單步操作：%%% 我的理解 第一次DFS時，獲取的信息有深度，父節點，子樹節點個數(SonAmount)，重兒子編號。
void dfs1(int n)//調用之前初始化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的樹節點數目比目前n的重兒子多 那么to是n的重兒子 } return;}第二次DFS時獲取的信息有DFS序號，新序號下的點權(邊權)，重鏈鏈首。注意到每個節點時，先DFS重兒子，這樣如果有一條由許多重兒子構成的重鏈，那么他們的dfs序號一定是連續的，重鏈頭也就是depth最小的那個節點。保證了線段樹區間更新。
void dfs2(int n, int prev){ Dfsnum[n]=++dfscount;//dfs序號 建線段樹用 TreeValue[dfscount]=Val[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); }}最后查詢時，查詢兩個節點ab，如果不在同一條重鏈上，那么往上跳，跳的方法就是不斷查詢a到fa=TopOfHeavyChain[a]，以及b和fb=TopOfHeavyChain[b]，a=father[fa]，b=father[fb]，到一條重鏈后最后查詢一次這條重鏈。就結束了。詳見代碼，說不太清。
代碼
#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的樹節點數目比目前n的重兒子多 那么to是n的重兒子 } return;}void dfs2(int n, int prev){ Dfsnum[n]=++dfscount;//dfs序號 建線段樹用 TreeValue[dfscount]=Val[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;}
