最近有点小颓废，每天休息也不是很好，实在没状态CF，好久没写题解了，写个水题来除除草
每天被寝室大神各种高端数据结构吓傻不已，前段时间学了下树链剖分，感觉还算比较好写。
size[u]表示以u为根的节点个数，dep[u]表示u的深度，pre[u]表示u的父节点，top[u]表示u所在重链的顶端节点，son[u]表示与在同一重链上的u的儿子节点，id[u]表示u在线段树中的位置，w[id[u]]表示线段树中的点权。
名词解释：
重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点。
重边：点v与其重儿子的连边。
轻边：点v与其轻儿子的连边。
重链：由重边连成的路径。
轻链：轻边
重点性质：
性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]；
性质2：从根到某一点的路径上轻链、重链的个数都不大于logn
算法实现：
显然可以dfs求出size,dep,pre,top,son,id，但是大数据可能出现爆栈的情况，于是我们可以用3次循环来求。
第一次正向循环求出pre,dep,再逆向循环求出size,再正向循环求出top,son,id。然后就可以将权值建立到线段树中
建完树就要开始我们核心算法了，比如更新u到v路径，设f1=top[u],f2=top[v],f1!=f2时，若dep[f1]>=dep[f2],更新u到pre[f1]的权值，然后u=pre[f1].当f1=f2时，再更新u到v的权值即可，操作均为logn的。
上代码：
[cpp] view plaincopyprint
#include
#include
#include
#include
#include
using namespace std;
const int N=30005;
int n,m,tot,head[N],next[N*2],to[N*2],val[N],pre[N],dep[N],q[N],size[N],son[N],top[N],w[N],id[N];
int MAX[N*4],sum[N*4];
bool v[N];
char s[20];
#define lc x << 1
#define rc (lc) + 1
inline void add(int u,int v)
{
to[++tot]=v;
next[tot]=head[u];
head[u]=tot;
}
void update(int x)
{
MAX[x]=max(MAX[lc],MAX[rc]);
sum[x]=sum[lc]+sum[rc];
}
void build(int x,int l,int r)
{
if(l==r)
{
MAX[x]=sum[x]=w[l];
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
update(x);
}
void change(int x,int l,int r,int u,int val)
{
if(l==r)
{
MAX[x]=sum[x]=val;
return ;
}
int mid=(l+r)>>1;
if(u<=mid) change(lc,l,mid,u,val);
else change(rc,mid+1,r,u,val);
update(x);
}
int qmax(int x,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r) return MAX[x];
int mid=(l+r)>>1;
int tmp1=INT_MIN;int tmp2=INT_MIN;
if(ql<=mid) tmp1=qmax(lc,l,mid,ql,qr);
if(qr>mid) tmp2=qmax(rc,mid+1,r,ql,qr);
return max(tmp1,tmp2);
}
int qsum(int x,int l,int r,int ql,int qr)
{
if(ql<=l && qr>=r) return sum[x];
int mid=(l+r)>>1;
int tmp1=0;int tmp2=0;
if(ql<=mid) tmp1=qsum(lc,l,mid,ql,qr);
if(qr>mid) tmp2=qsum(rc,mid+1,r,ql,qr);
return tmp1+tmp2;
}
inline int gmax(int a,int b)
{
int tmp=INT_MIN;
while(top[a]!=top[b])
{
if(dep[top[a]]
a=pre[top[a]];
}
if(id[a]>id[b]) swap(a,b);
tmp=max(tmp,qmax(1,1,n,id[a],id[b]));
return tmp;
}
inline int gsum(int a,int b)
{
int tmp=0;
while(top[a]!=top[b])
{
if(dep[top[a]]
a=pre[top[a]];
}
if(id[a]>id[b]) swap(a,b);
tmp+=qsum(1,1,n,id[a],id[b]);
return tmp;
}
int main()
{
scanf("%d",&n);
int a,b;
for(int i=1;i
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
v[dep[1]=q[0]=1]=true;
int r=0;tot=0;
for(int l=0;l<=r;++l)
for(int k=head[q[l]];k;k=next[k])
{
if(!v[to[k]])
{
v[to[k]]=true;
dep[q[++r]=to[k]]=dep[q[l]]+1;
pre[q[r]]=q[l];
}
}
for(int i=r;i>=0;--i)
{
size[pre[q[i]]]+=++size[q[i]];
if(size[q[i]]>size[son[pre[q[i]]]])
son[pre[q[i]]]=q[i];
}
for(int i=0;i<=r;++i)
{
if(!top[q[i]])
for(int k=q[i];k;k=son[k])
{
top[k]=q[i];
w