學習樹鏈剖分的第一題，第二個dfs忘記遞歸了（太蠢），re了兩發，改過來以后就1A了。

學習樹鏈剖分可以參考這篇博客：http://blog.sina.com.cn/s/blog_7a1746820100wp67.html 個人感覺寫得非常好！！！

樹鏈剖分聽起來很吊，其實就是把數邊扔到線段樹上，然后搞出一點事情來。主要就是一個重兒子，重鏈，從而使復雜度降到了(logn)。這個非常關鍵。關于初始化建樹：先剖分，求出size,son,w,top,fa,dep數組，就能把樹鏈扔到線段樹樹上實現了，這個過程也就是兩個dfs實現。然后就是簡單的區間修改的問題了。（再次感覺那篇博客寫得太好了）

樹的邊權的問題可以轉化為樹鏈剖分的問題！！！

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cmath> #include <map> #define LL long long #define FOR(i,x,y) for(int i = x;i < y;i ++) #define IFOR(i,x,y) for(int i = x;i > y;i --) #define lrt rt<<1 #define rrt rt<<1|1 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define MAXN 11000using namespace std;int n,val[MAXN];int head[MAXN<<1],edge_cnt; map <int,int> mat;struct Edge{int u,v,idd,value;int nt; }edge[MAXN<<1];void add_edge(int u,int v,int idd){edge[edge_cnt].u = u;edge[edge_cnt].v = v;edge[edge_cnt].idd = idd;edge[edge_cnt].nt = head[u];head[u] = edge_cnt++; }int sz[MAXN],son[MAXN],fa[MAXN],dep[MAXN],top[MAXN],id[MAXN],w[MAXN],val0[MAXN],totw;void dfs1(int u,int father,int depth){sz[u] = 1; dep[u] = depth; fa[u] = father;int idd = -1,maxx = -1;for(int i = head[u];i != -1;i = edge[i].nt){int v = edge[i].v;if(v == father) continue;id[v] = edge[i].idd;dfs1(v,u,depth+1);sz[u] += sz[v];if(sz[v] > maxx) {idd = v;maxx = sz[v];}}son[u] = idd; }void dfs2(int u,int father){if(son[u] == -1) return;top[son[u]] = top[u];w[son[u]] = ++totw;val[totw] = val0[id[son[u]]];mat[id[son[u]]] = totw;dfs2(son[u],u);for(int i = head[u];i != -1;i = edge[i].nt){int v = edge[i].v;if(v == father) continue;if(v == son[u]) continue;top[v] = v;w[v] = ++totw;val[totw] = val0[id[v]];mat[id[v]] = totw;dfs2(v,u);} }struct Tree{int l,r;int maxx; }tree[MAXN<<2];void PushUp(int rt){tree[rt].maxx = max(tree[lrt].maxx,tree[rrt].maxx); }void Build(int rt,int l,int r){tree[rt].l = l; tree[rt].r = r;if(l == r){tree[rt].maxx = val[l];return;}int mid = (l+r)>>1;Build(lson);Build(rson);PushUp(rt); }void Modify(int rt,int x,int value){if(tree[rt].l == tree[rt].r){tree[rt].maxx = value;return;}int mid = (tree[rt].l + tree[rt].r)>>1;if(x <= mid) Modify(lrt,x,value);else Modify(rrt,x,value);PushUp(rt); }int Query(int rt,int l,int r){if(tree[rt].l == l && tree[rt].r == r){return tree[rt].maxx;}int mid = (tree[rt].l + tree[rt].r)>>1;if(r <= mid) return Query(lrt,l,r);else if(l > mid) return Query(rrt,l,r);else return max(Query(lson),Query(rson)); }int solve(int l,int r){int ans = -1;while(top[l] != top[r]){if(dep[top[l]] >= dep[top[r]]){ans = max(ans,Query(1,w[top[l]],w[l]));l = fa[top[l]];}else{ans = max(ans,Query(1,w[top[r]],w[r]));r = fa[top[r]];}}if(l == r) return ans;if(dep[l] >= dep[r]){return max(ans,Query(1,w[r]+1,w[l]));}else return max(ans,Query(1,w[l]+1,w[r])); }int main(){//freopen("test.in","r",stdin);int T;scanf("%d",&T);while(T--){scanf("%d",&n);int u,v,value;memset(head,-1,sizeof(head));edge_cnt = 0;FOR(i,1,n){scanf("%d%d%d",&u,&v,&value);add_edge(u,v,i);add_edge(v,u,i);val0[i] = value;}dfs1(1,-1,1);totw = 0;top[1] = 1;dfs2(1,-1);Build(1,1,totw);char op[10];while(~scanf("%s",op) && strcmp(op,"DONE")){if(strcmp(op,"QUERY") == 0){int l,r;scanf("%d%d",&l,&r);printf("%d\n",solve(l,r));}else{int x,value;scanf("%d%d",&x,&value);Modify(1,mat[x],value);}}}return 0; }

版權聲明：本文為博主原創文章，未經博主允許不得轉載。

轉載于:https://www.cnblogs.com/hqwhqwhq/p/4811885.html

總結

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

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