SPOJ QTREE 树链剖分边上剖分

本文主要是介绍SPOJ QTREE 树链剖分边上剖分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://bak2.vjudge.net/problem/13013/origin

#include <cstdio>
#include <cstring>
#include <algorithm>
#define sf scanf
#define pf printf
using namespace std;/** Edge */
const int maxn = 10000 + 50;
int n;
struct Edge{int v,c,pre;
}Es[maxn * 2];
int head[maxn],TOT_EDGE;
void EDGE_INIT(){memset(head,-1,sizeof head);TOT_EDGE = 0;
}
inline void Add_Edge(int u,int v,int c){Es[TOT_EDGE].v = v;Es[TOT_EDGE].c = c;Es[TOT_EDGE].pre = head[u];head[u] = TOT_EDGE++;
}/** TreeSplit */
int son[maxn],size[maxn],fa[maxn],dep[maxn];
int top[maxn],tid[maxn],rank[maxn],tot;
int DFS(int rt){dep[rt] = dep[fa[rt]] + 1;son[rt] = 0;size[rt] = 1;for(int i = head[rt];~i;i = Es[i].pre){int v = Es[i].v;if(v != fa[rt]){fa[v] = rt;size[rt] += DFS(v);if(size[son[rt]] < size[v]) son[rt] = v;}}return size[rt];
}void Split(int rt,int tp){top[rt] = tp;tid[rt] = tot++;rank[tid[rt]] = rt;if(son[rt]){Split(son[rt],tp);for(int i = head[rt];~i;i = Es[i].pre){int v = Es[i].v;if(v != fa[rt] && v != son[rt]) Split(v,v);}}
}inline void TreeLineSplit(){size[0] = 0;fa[1] = 1;dep[0] = 0;DFS(1);tot = 0;Split(1,1);
}/** SegTree */
#define lson rt << 1 , l , mid
#define rson rt << 1 | 1,mid + 1,r
int MAX[maxn << 2],num[maxn];
void PushUp(int rt){MAX[rt] = max(MAX[rt << 1],MAX[rt << 1 | 1]);
}void Build(int rt,int l,int r){if(l == r){MAX[rt] = num[l];return;}int mid = l + r >> 1;Build(lson);Build(rson);PushUp(rt);
}void Update(int rt,int l,int r,int x,int c){if(l == r){MAX[rt] = c;return;}int mid = l + r >> 1;if(x <= mid) Update(lson,x,c);else Update(rson,x,c);PushUp(rt);
}int Query(int rt,int l,int r,int L,int R){if(L <= l && R >= r) return MAX[rt];int mid = l + r >> 1;int ret = 0;if(L <= mid) ret = max(ret,Query(lson,L,R));if(R > mid) ret = max(ret,Query(rson,L,R));return ret;
}inline void GetNumAr(){for(int i = 0;i < TOT_EDGE;i += 2){int u = Es[i].v,v = Es[i + 1].v,c = Es[i].c;if(dep[v] < dep[u]) swap(u,v);num[tid[v]] = c;}
}/** ANS */
inline void CHANGE(int x,int c){int u = Es[(x - 1) * 2].v,v = Es[(x - 1) * 2 + 1].v;if(dep[v] < dep[u]) swap(u,v);Update(1,1,n - 1,tid[v],c);
}
inline int Ans_Query(int u,int v){int ret = 0;while(top[u] != top[v]){if(dep[top[v]] < dep[top[u]]) swap(u,v);ret = max(ret,Query(1,1,n - 1,tid[top[v]],tid[v]));v = fa[top[v]];}if(u == v) return ret;if(dep[v] < dep[u]) swap(u,v);return max(ret,Query(1,1,n - 1,tid[u] + 1,tid[v]));
}char op[10];
int main(){
//    freopen("in.txt","r",stdin);int T;sf("%d",&T);while( T-- ){sf("%d",&n);EDGE_INIT();for(int i = 1;i < n;++i){int u,v,c;sf("%d%d%d",&u,&v,&c);Add_Edge(u,v,c);Add_Edge(v,u,c);}TreeLineSplit();GetNumAr();Build(1,1,n - 1);int x,y;while( sf("%s",op) ){if(op[0] == 'D') break;sf("%d%d",&x,&y);if(op[0] == 'Q') pf("%d\n",Ans_Query(x,y));else CHANGE(x,y);}}return 0;
}