SPOJ QTREE - Query on a tree （树链剖分）

SPOJ QTREE - Query on a tree （树链剖分）

Description

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3…N-1.We will ask you to perfrom some instructions of the following form:CHANGE i ti : change the cost of the i-th edge to tiQUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.For each test case:In the first line there is an integer N (N <= 10000),In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),The next lines contain instructions “CHANGE i ti” or “QUERY a b”,The end of each test case is signified by the string “DONE”.There is one blank line between successive tests.

Output

For each “QUERY” operation, write one integer representing its result.

Example

Input:131 2 12 3 2QUERY 1 2CHANGE 1 3QUERY 1 2DONEOutput:13

题意

给出一棵树，有两种操作：修改边权与查询 ​​u->v​​ 路径边权最大值。

思路

树链剖分，将树剖分为若干条链，利用线段树去维护每一条链即可。（以后在其他文章中介绍这种算法）

AC 代码

#include#include#include#includeusing namespace std;const int maxn = 10010;struct Edge{ int to; int next;} edge[maxn<<1];int head[maxn],tot; //链式前向星存储int top[maxn]; //v所在重链的顶端节点int fa[maxn]; //父亲节点int deep[maxn]; //节点深度int num[maxn]; //以v为根的子树节点数int p[maxn]; //v与其父亲节点的连边在线段树中的位置int fp[maxn]; //与p[]数组相反int son[maxn]; //重儿子int pos;int e[maxn][3];void init(){ memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son)); tot=0; pos=0;}void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++;}void dfs1(int u,int pre,int d) //第一遍dfs，求出 fa,deep,num,son (u为当前节点,pre为其父节点,d为深度){ deep[u]=d; fa[u]=pre; num[u]=1; for(int i=head[u]; i!=-1; i=edge[i].next) //遍历u的邻接点 { int v=edge[i].to; if(v!=pre) { dfs1(v,u,d+1); num[u]+=num[v]; if(son[u]==-1||num[v]>num[son[u]]) //寻找重儿子 son[u]=v; } }}void dfs2(int u,int sp) //第二遍dfs，求出 top,p{ top[u]=sp; p[u]=pos++; fp[p[u]]=u; if(son[u]!=-1) //如果当前点存在重儿子，继续延伸形成重链 dfs2(son[u],sp); else return; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(v!=son[u]&&v!=fa[u]) //遍历所有轻儿子新建重链 dfs2(v,v); }}int maxx[maxn<<2],dep=1; //存储线段树各节点的值以及最底层元素个数void build() //一棵完美二叉树的初始化{ while(dep1) { o>>=1; maxx[o]=max(maxx[o<<1],maxx[(o<<1)^1]); }}int query(int a,int b,int k,int l,int r) //查询[a,b]最大值，[l,r]为当前查询区间，k为当前所在节点{ if(r=r)return maxx[k]; //如果[a,b]包含[l,r]返回当前节点的值 else { int v1=query(a,b,k<<1,l,(l+r)>>1); //左子树 int v2=query(a,b,(k<<1)^1,((l+r)>>1)+1,r); //右子树 return max(v1,v2); }}int find(int u,int v){ int f1=top[u],f2=top[v]; int tmp=0; while(f1!=f2) { if(deep[f1]deep[v])swap(u,v); return max(tmp,query(p[son[u]],p[v],1,0,dep-1));}int main(){ ios::sync_with_stdio(false); int T; cin>>T; while(T--) { int n; cin>>n; init(); for(int i=0; i>e[i][j]; addedge(e[i][0],e[i][1]); addedge(e[i][1],e[i][0]); } dfs1(1,0,0); dfs2(1,1); build(); for(int i=0; ideep[e[i][1]]) swap(e[i][0],e[i][1]); update(p[e[i][1]],e[i][2]); } char op[10]; while(cin>>op) { if(op[0]=='D')break; int a,b; cin>>a>>b; if(op[0]=='C') update(p[e[a-1][1]],b); else if(op[0]=='Q') cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。