第一篇博文，认真口糊一下。
首先一点点关于树链剖分。
目的：解决在树上进行插点问线，插线问点的一系列问题 树链：树上的路径 剖分：把路径（即树链）分为重链和轻链 定义size[x]为以x为根的子树的节点个数 令v为u的儿子节点中size最大的节点，那么边 u-v 被称为重边 除了重边之外的边称为轻边 性质： 1.对于轻边（u，v），size[v]<=size[u]/2 2.从根到某一点的路径上，不超过O(log N) 条轻边，不超过O（log N）条重边然后是例题。
Query on a tree [题目链接](https://vjudge.net/problem/SPOJ-QTREE) 题目大意： 给你一棵树，所给的树每两点之间存在边权，现给出两种操作，修改某两点之间的边权，或者给出询问，对于（u,v）路径上的最大边权。 主要思路： 将边权转化为点权处理，从根开始dfs，将每条边的权值赋到向下的一个节点上，最后再把根的值赋为-∞即可。树剖模板题。最后是代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int T,n,tot,Head[20010],label,Next[20010],tree[20010],val[20010],a[80080],f[10010],bian[10010]; int size[10010],son[10010],num[10010],tid[10010],top[10010],fa[10010],dep[10010],number[20010]; bool visit[10010]; void Add(int x,int y,int z,int Num) { tot++; Next[tot]=Head[x]; Head[x]=tot; tree[tot]=y; val[tot]=z; number[tot]=Num; } void up(int x) { a[x]=max(a[x*2],a[x*2+1]); } void build(int id,int l,int r) { if (l==r) { a[id]=f[num[l]]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); up(id); } void Change_it(int x,int y,int d,int id,int l,int r)//此题单点修改 { if (l>y||r<x) return; if (l>=x&&r<=y) { a[id]=d; return; } int mid=(l+r)/2; Change_it(x,y,d,id*2,l,mid); Change_it(x,y,d,id*2+1,mid+1,r); up(id); } int Query_it(int x,int y,int id,int l,int r) { if (l>y||r<x) return(-1<<29); if (l>=x&&r<=y) return a[id]; int mid=(l+r)/2; int ans=max(Query_it(x,y,id*2,l,mid),Query_it(x,y,id*2+1,mid+1,r)); return ans; } void Find_heavy_edge(int x,int father,int depth) { fa[x]=father;dep[x]=depth; visit[x]=true;size[x]=1;son[x]=0; int maxsize=0; for (int i=Head[x];i;i=Next[i]) if (!visit[tree[i]]) { f[tree[i]]=val[i];bian[number[i]]=tree[i]; Find_heavy_edge(tree[i],x,depth+1); size[x]+=size[tree[i]]; if (maxsize<size[tree[i]]) { maxsize=size[tree[i]]; son[x]=tree[i]; } } } void Connect_heavy_edge(int x,int ancestor) { visit[x]=true; label++;tid[x]=label;num[label]=x;top[x]=ancestor; if (son[x]!=0) Connect_heavy_edge(son[x],ancestor); for (int i=Head[x];i;i=Next[i]) if (!visit[tree[i]]) { Connect_heavy_edge(tree[i],tree[i]); } } int Query(int x,int y) { int ans=-1<<29; while(top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,Query_it(tid[top[x]],tid[x],1,1,n)); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=max(ans,Query_it(tid[x]+1,tid[y],1,1,n)); return ans; } int main() { scanf("%d",&T); for (int cas=1;cas<=T;cas++) { scanf("%d",&n); tot=0; for (int i=1;i<=n;i++) Head[i]=0; for (int i=1;i<=n-1;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); Add(x,y,z,i);Add(y,x,z,i); } int root=1; f[root]=-1<<27; label=0; for (int i=1;i<=n;i++) visit[i]=false; Find_heavy_edge(root,0,1); for (int i=1;i<=n;i++) visit[i]=false; Connect_heavy_edge(root,root); build(1,1,n); char s[10]; int x,y; while (true) { scanf("%s",s); if (s[0]=='D') break; scanf("%d%d",&x,&y); if (s[0]=='Q') printf("%d\n",Query(x,y)); else Change_it(tid[bian[x]],tid[bian[x]],y,1,1,n); } } return 0; } （转自 wuli可亲可敬的何开同学，(http://blog.csdn.net/yuyaohekai/)）