树链剖分学习
https://blog.csdn.net/u013368721/article/details/39734871
https://www.cnblogs.com/George1994/p/7821357.html
核心：节点u的轻儿子为v 轻儿子的性质：size[v] <= size[u] / 2
故：每走一条轻链，节点数减少一半
又因：两个节点之间的路径，必为重链和轻边交替
故：从根结点到树上任意点经过的轻边以及重链都不会超过logn条
http://acm.hust.edu.cn/vjudge/problem/13013
树链剖分模版题
题意：
有一棵N个节点的树（1<=N<=10000），N-1条边，边的编号为1~N-1，每条边有一个权值，要求模拟两种操作：
1：QUERY x y 求节点x和节点y之间的路径中权值最大的边。
2：CHANGE p k修改第p条边的权值为k。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=;
char s[];
struct trnode{
int lc,rc,l,r,c;
}t[*N];
struct node{
int x,y,d,next;
}a[*N],b[N];
int n,tl,z,len;
int first[N],tot[N],son[N],fa[N],dep[N],ys[N],top[N]; int maxx(int x,int y){return x>y ? x:y;} void ins(int x,int y,int d)
{
len++;
a[len].x=x;a[len].y=y;a[len].d=d;
a[len].next=first[x];first[x]=len;
} int build_tree(int l,int r)
{
int x=++tl;
t[x].l=l;t[x].r=r;t[x].c=;
t[x].lc=t[x].rc=-;
if(l<r)
{
int mid=(l+r)>>;
t[x].lc=build_tree(l,mid);
t[x].rc=build_tree(mid+,r);
}
return x;
} void change(int x,int p,int c)
{
if(t[x].l==t[x].r) {t[x].c=c;return;}
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(p<=mid) change(lc,p,c);
else change(rc,p,c);
t[x].c=maxx(t[lc].c,t[rc].c);
} int query(int x,int l,int r)
{
if(t[x].l==l && t[x].r==r) return t[x].c;
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(r<=mid) return query(lc,l,r);
else if(l>mid) return query(rc,l,r);
return maxx(query(lc,l,mid),query(rc,mid+,r));
} void dfs1(int x)
{
tot[x]=;son[x]=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa[x]) continue;
fa[y]=x;
dep[y]=dep[x]+;
dfs1(y);
if(tot[son[x]]<tot[y]) son[x]=y;
tot[x]+=tot[y];
}
} void dfs2(int x,int tp)
{
ys[x]=++z;top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
} int solve(int x,int y)
{
int tx=top[x],ty=top[y],ans=;
while(tx!=ty)
{
if(dep[tx]>dep[ty]) swap(tx,ty),swap(x,y);//debug swap(x,y)之前漏了
ans=maxx(ans,query(,ys[ty],ys[y]));
y=fa[ty];ty=top[y];
}
if(x==y) return ans;
else
{
if(dep[x]>dep[y]) swap(x,y);
return maxx(ans,query(,ys[son[x]],ys[y]));
}
} int main()
{
freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
len=;tl=;z=;dep[]=;tot[]=;
memset(fa,,sizeof(fa));
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].d);
ins(b[i].x,b[i].y,b[i].d);
ins(b[i].y,b[i].x,b[i].d);
}
dfs1();
dfs2(,);
build_tree(,z);
for(int i=;i<n;i++) if(dep[b[i].x]>dep[b[i].y]) swap(b[i].x,b[i].y);
for(int i=;i<n;i++) change(,ys[b[i].y],b[i].d);
while()
{
scanf("%s",s);
int x,y,d;
if(s[]=='Q')
{
scanf("%d%d",&x,&y);
printf("%d\n",solve(x,y));
}
if(s[]=='C')
{
scanf("%d%d",&x,&d);
change(,ys[b[x].y],d);
}
if(s[]=='D') break;
}
}
return ;
}