#tree
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 ti orQUERY a b : ask for the maximum edge cost on the path from node a to node bThe 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.
For each "QUERY" operation, write one integer representing its result.
题意：输入一个n，给你n-1条边，然后是操作，QUERY a b：查询a，b连点之间边得最大值；CHANGE a b：修改第a条边的值为b：DONE：结束；
这题是树链剖分的模板题，如果树链剖分不懂推荐一篇博客：http://blog.csdn.net/bobodem/article/details/52330316
刚开始学这个东西是很难理解，不能着急，好好理解每个数组代表的是什么，并且树链剖分会分边权和点权，这题是边权，两个代码有点小差别，这类题没理解透彻很容易写错并且不好找bud，耐心看吧；
AC代码：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define MAX 10010 using namespace std; int t,n,tot,pos,head[MAX], int dep[MAX],top[MAX],son[MAX],sz[MAX],fa[MAX],id[MAX]; //节点在树中的深度，节点的根节点，节点的重儿子，以该节点为根节点的子树的大小，节点的父节点，边在线段树中的位置； struct Edge//边的结构体 { int to; int next; }edge[MAX*2]; struct ee//输入的边 { int x; int y; int val; }e[MAX]; struct node//线段树 { int l; int r; int val; }segtree[MAX*4]; void add_edge(int u,int v) { edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs1(int u,int f,int deep) { dep[u]=deep; fa[u]=f; son[u]=0; sz[u]=1; for(int i=head[u];i!=-1;i=edge[i].next)//遍历与u相连的所有的点 { int ff=edge[i].to; if(ff==f)continue; dfs1(ff,u,deep+1); sz[u]+=sz[ff]; if(sz[son[u]]<sz[ff]) son[u]=ff; } } void dfs2(int u,int tp) { top[u]=tp; id[u]=pos++; if(son[u]) dfs2(son[u],tp); for(int i=head[u];i!=-1;i=edge[i].next) { int ff=edge[i].to; if(ff==son[u]||ff==fa[u])continue; dfs2(ff,ff); } } //线段树的操作 void pushup(int root) { segtree[root].val=max(segtree[root<<1].val,segtree[root<<1|1].val); } void build(int root,int l,int r) { segtree[root].l=l; segtree[root].r=r; segtree[root].val=0; if(l==r) return; int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); } void update(int root,int p,int val) { int ll=segtree[root].l; int rr=segtree[root].r; if(ll==rr) { segtree[root].val=val; return; } int mid=(ll+rr)>>1; if(p<=mid) update(root<<1,p,val); else update(root<<1|1,p,val); pushup(root); } int query(int root,int l,int r) { int ll=segtree[root].l; int rr=segtree[root].r; if(l<=ll&&rr<=r) return segtree[root].val; int mid=(ll+rr)>>1; int ans=-1; if(l<=mid)ans=max(ans,query(root<<1,l,r)); if(r>mid)ans=max(ans,query(root<<1|1,l,r)); return ans; } // int Yougth(int u,int v) { int tp1=top[u]; int tp2=top[v]; int ans=-1; while(tp1!=tp2) { if(dep[tp1]<dep[tp2]) { swap(u,v); swap(tp1,tp2); } ans=max(ans,query(1,id[tp1],id[u])); u=fa[tp1]; tp1=top[u]; } if(u==v)return ans; if(dep[u]>dep[v])swap(u,v); ans=max(ans,query(1,id[son[u]],id[v])); return ans; } void init() { tot=0; pos=0; memset(head,-1,sizeof(head)); } int main() { scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val); add_edge(e[i].x,e[i].y); add_edge(e[i].y,e[i].x); } dfs1(1,0,0); dfs2(1,1); build(1,1,pos); for(int i=1;i<n;i++) { if(dep[e[i].x]<dep[e[i].y]) swap(e[i].x,e[i].y); update(1,id[e[i].x],e[i].val); } char op[30]; int u,v; while(scanf("%s",op)==1) { if(op[0]=='D')break; scanf("%d%d",&u,&v); if(op[0]=='Q')printf("%d\n",Yougth(u,v)); if(op[0]=='C')update(1,id[e[u].x],v); } } return 0; }
