树链剖分的模板题:在点带权树树上维护路径和,最大值和单点修改
这里给出几个定义
以任意点为根,然后记 size (u ) 为以 u 为根的子树的结点个数,令 v 为 u 所有
儿子中 size 值最大的一个儿子,则 ( u , v ) 为重边, v 称为 u 的重儿子。 u 到其余儿子的边为轻边。
根据定义:任何一个点属于且仅属于一条重链(这里一个点也算是重链)
我们称某条路径为重路径(链),当且仅当它全部由重边组成且端点两边没有重边了。
所以我们可以把这个棵树分成若干个重链,经过证明重链的个数不超过O(logn)
以下给出几个性质可以帮助理解:
性质1:如果 ( u , v ) 为轻边,则 size ( v ) <= size ( u ) / 2
性质2:从根到某一点 V 的路径上的轻边个数不大于 O (log n ) 。
性质3:我们称某条路径为重路径(链),当且仅当它全部由重边组成。那么对于
每个点到根的路径上都不超过 O (log n ) 条轻边和 O (log n ) 条重路径。
如果我们可以用数据结构维护每条重链,就可以在O(nlog^2n)的复杂度内完成询问
接下来给出算法的具体实现步骤
核心:用dfs处理dfs序保证每条重链的点在dfs序列的编号连续,用线段树维护每个重链所在dfs序列
用两次DFS计算7个值
fa[x]:x的父亲
deep[x]:x的深度
sz[x]:以x为根的子树大小
son[x]:x的重儿子
top[x]:x所在的重链的深度最小的节点编号(显然重链是一条深度递增的链)
pos[x]:x在序列中的下标
idx[x]:序列的第x位置对应树中节点编号
这个可以用两次dfs维护出来.
接下来考虑我们怎么把(u,v)的路径拆分成若干个重链:
显然找路径是求LCA的过程
我们始终令deep[top[u]]>deep[top[v]],
当top[v]=top[u] 时,显然他们属于同一个重链,我们直接query就好
当top[u]!=top[v]时,我们让u去他top的fa,这样就到了新的重链
而且这次操作可以在logn内完成这部分路径的查询,如此下去,一定能到他们top相同的时候.就OK啦
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 30010
#define INF 100000000
using namespace std;
int ecnt,head[N],q,val[N],a,b,fa[N],deep[N],son[N],sz[N],top[N],tot,pos[N],indx[N],n;
//数组的定义见上
char s[N];
int read()
{
int ret=,neg=;
char j=getchar();
for (;j>'' || j<'';j=getchar())
if (j == '-') neg=-;
for (;j>='' && j<='';j=getchar())
ret=ret*+j-'';
return ret*neg;
}
struct adj//边
{
int nxt,v;
}e[*N];
struct node//线段树的点
{
int l,r,sum,mx;
}t[*N];
inline void add(int u,int v)//加边
{
e[++ecnt].v=v;
e[ecnt].nxt=head[u];
head[u]=ecnt;
e[++ecnt].v=u;
e[ecnt].nxt=head[v];
head[v]=ecnt;
}
void dfs1(int x,int father,int depth)//第一次dfs处理深度,子树大小,重儿子是谁
{
deep[x]=depth,fa[x]=father,sz[x]=;
for (int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v==father) continue;
dfs1(v,x,depth+);
sz[x]+=sz[v];
if (!son[x] || sz[v]>sz[son[x]]) son[x]=v;
}
}
void dfs2(int x,int TOP)//第二次dfs处理dfs序和top[i]
{
top[x]=TOP,pos[x]=++tot,indx[pos[x]]=x;
if (son[x]!=) dfs2(son[x],TOP);//首先搜重儿子保证这个重链上的点的dfs序连续
for (int i=head[x];i;i=e[i].nxt)
if (e[i].v==son[x] || e[i].v==fa[x]) continue;
else dfs2(e[i].v,e[i].v);
}
void pushup(int p)//emmm
{
t[p].mx=max(t[p<<].mx,t[p<<|].mx);
t[p].sum=t[p<<].sum+t[p<<|].sum;
}
void build(int p,int l,int r)//线段树
{
t[p].l=l,t[p].r=r;
if (l==r)
t[p].sum=t[p].mx=val[indx[l]];//当前的左端点实际上要维护是dfs序对应的节点编号
else
{
int mid=l+r>>;
build(p<<,l,mid);
build(p<<|,mid+,r);
pushup(p);
}
}
void modify(int p,int l,int k)
{
if (t[p].l==l && t[p].r==t[p].l)
t[p].sum=k,t[p].mx=k;
else
{
int mid=t[p].l+t[p].r>>;
if (l<=mid) modify(p<<,l,k);
else modify(p<<|,l,k);
pushup(p);
}
}
int querySum(int p,int l,int r)
{
if (t[p].l==l && t[p].r==r)
return t[p].sum;
int mid=t[p].l+t[p].r>>;
if (r<=mid) return querySum(p<<,l,r);
if (l>mid) return querySum(p<<|,l,r);
return querySum(p<<,l,mid)+querySum(p<<|,mid+,r);
}
int queryMax(int p,int l,int r)
{
if (t[p].l==l && t[p].r==r)
return t[p].mx;
int mid=t[p].l+t[p].r>>;
if (r<=mid) return queryMax(p<<,l,r);
if (l>mid) return queryMax(p<<|,l,r);
return max(queryMax(p<<,l,mid),queryMax(p<<|,mid+,r));
}
int pathSum(int u,int v)
{
int ret=;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);//保证top[u]深度较大
ret+=querySum(,pos[top[u]],pos[u]);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);//最后别忘了走pos[u]和pos[v]之间的位置
return ret+querySum(,pos[u],pos[v]);
}
int pathMax(int u,int v)
{
int ret=-INF;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ret=max(ret,queryMax(,pos[top[u]],pos[u]));
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
return max(ret,queryMax(,pos[u],pos[v]));
}
int main()
{
n=read();
for (int i=;i<n;i++)
add(read(),read());
for (int i=;i<=n;i++)
val[i]=read();
dfs1(,,);
dfs2(,);
build(,,n);
q=read();
while (q--)
{
scanf("%s%d%d",s,&a,&b);
if (s[]=='C')
modify(,pos[a],b);
else if (s[]=='M')
printf("%d\n",pathMax(a,b));
else printf("%d\n",pathSum(a,b));
}
return ;
}