这是树链剖分的入门题，也是我学树链剖分的第一题。
树链剖分：就是把树中和线段树联系起来，求（u，v）路径中权值的最大值和其路径的权值和。
入门blog:http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
https://quartergeek.com/summary-of-heavy-light-decomposition/
kuangbin 菊苣的专题训练：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28982#overview
我的第一树链
#include<bits/stdc++.h>
using namespace std;
#define N 30010 struct Edge
{
int to,next;
}edge[N*]; int head[N],tot;
int top[N],fa[N],deep[N],num[N],p[N],fp[N],son[N],pos; void init()
{
tot=;
memset(head,-,sizeof(head));
pos=;
memset(son,-,sizeof(son));
} 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)
{
deep[u]=d;
fa[u]=pre;
num[u]=;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (v!=pre)
{
dfs1(v,u,d+);
num[u]+=num[v];
if (son[u]==-||num[v]>num[son[u]])
son[u]=v;
}
}
} void getpos(int u,int sp)
{
top[u]=sp;
p[u]=pos++;
fp[p[u]]=u;
if (son[u]==-) return;
getpos(son[u],sp);
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (v!=son[u]&&v!=fa[u]) getpos(v,v);
}
}
struct node
{
int l,r;
int sum;
int Max;
}tree[N*];
void push_up(int i)
{
tree[i].sum=tree[i<<].sum+tree[i<<|].sum;
tree[i].Max=max(tree[i<<].Max,tree[i<<|].Max);
}
int s[N]; void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
if (l==r)
{
tree[i].sum=tree[i].Max=s[fp[l]];
return;
} int mid=(l+r)>>;
build(i<<,l,mid);
build(i<<|,mid+,r);
push_up(i);
}
void update(int i,int k,int val)
{
if (tree[i].l==k&&tree[i].r==k)
{
tree[i].sum=tree[i].Max=val;
return;
}
int mid=(tree[i].l+tree[i].r)/;
if (k<=mid) update(i<<,k,val);
else update(i<<|,k,val);
push_up(i);
} int query_max(int i,int l,int r)
{
if (tree[i].l==l&&tree[i].r==r)
return tree[i].Max;
int mid=(tree[i].l+tree[i].r)/;
if (r<=mid) return query_max(i<<,l,r);
else if (l>mid) return query_max(i<<|,l,r);
else return max(query_max(i<<,l,mid),query_max(i<<|,mid+,r));
} int query_sum(int i,int l,int r)
{
if (tree[i].l==l&&tree[i].r==r)
return tree[i].sum;
int mid=(tree[i].l+tree[i].r)/;
if (r<=mid) return query_sum(i<<,l,r);
else if (l>mid) return query_sum(i<<|,l,r);
else return query_sum(i<<,l,mid)+query_sum(i<<|,mid+,r);
} int findmax(int u,int v)
{
int f1=top[u],f2=top[v]; int tmp=-;
while (f1!=f2)
{
if (deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp=max(tmp,query_max(,p[f1],p[u]));
u=fa[f1];
f1=top[u];
}
if (deep[u]>deep[v]) swap(u,v);
return max(tmp,query_max(,p[u],p[v]));
} int findsum(int u,int v)
{
int f1=top[u],f2=top[v];
int tmp=;
while (f1!=f2)
{
if (deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp+=query_sum(,p[f1],p[u]);
u=fa[f1];
f1=top[u];
}
if (deep[u]>deep[v]) swap(u,v);
return tmp+query_sum(,p[u],p[v]);
} int main()
{
int n;
int q;
char op[];
int u,v;
while(scanf("%d",&n) == )
{
init();
for(int i = ;i < n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i = ;i <= n;i++)
scanf("%d",&s[i]);
dfs1(,,);
getpos(,);
build(,,pos-);
scanf("%d",&q);
while(q--)
{
scanf("%s%d%d",op,&u,&v);
if(op[] == 'C')
update(,p[u],v);//修改单点的值
else if(strcmp(op,"QMAX") == )
printf("%d\n",findmax(u,v));//查询u->v路径上点权的最大值
else printf("%d\n",findsum(u,v));//查询路径上点权的和
}
}
return ;
}
份代码：