原题链接：P4114 Qtree1
思路
树链剖分裸题，将边权移至儿子节点作为点权，树剖后线段树维护单点修改和区间最大值即可。
由于是首次撰写树剖题解，详细写一下树链剖分的学习笔记。
树链剖分
在这里指重链剖分。其实就是两遍dfs。
一些概念
- 重儿子：子树大小最大的儿子
- 重链：从某点出发，一直走重儿子直到叶子节点所经过的链
- 轻边：不属于任何一条重链的边
图中红点标记为每个重链的最高点（注意，有的重链只有一个点），加粗的边构成的链是重链，其余边是轻边。
算法过程
前面已经说了是两遍dfs。
- 任选根节点，第一遍dfs确定父亲同时维护深度
dep、大小siz和重儿子son - 第二遍dfs记录dfs序
dfn和每个节点所属重链的开始节点top，有时还需要维护离开时的标记end
也就是这样：
int dep[MAXN],fat[MAXN],siz[MAXN],son[MAXN],tim=0;
int dfn[MAXN],end[MAXN],top[MAXN];
void dfs1(int u,int f){
u[dep]=f[dep]+1;
u[fat]=f;
u[siz]=1;
u[son]=0;
for(int i=u[head],v;i;i=i[nxt])
if((v=to[i])!=f){
dfs1(v,u);
u[siz]+=v[siz];
if(v[siz]>u[son][siz])u[son]=v;
}
}
void dfs2(int u,int f){
u[dfn]=++tim;
u[top]=(u==f[son])?f[top]:u;
if(u[son])dfs2(u[son],u);
for(int i=u[head],v;i;i=i[nxt])
if((v=i[to])!=f&&v!=u[son])dfs2(v,u);
u[end]=tim;
}随便初始化然后直接执行dfs1(1,0);dfs2(1,0);，完成后就可以利用dfn数组在线段树上乱搞啦~
附注与代码
注意，由于本题是把边权移至子节点来做，所以线段树区间查询时不应包含LCA，直接两侧取max即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100003;
int n;
//白调了，无向图两倍大小，请
int head[MAXN<<1],nxt[MAXN<<1],to[MAXN<<1],cnt=0,tim=0;
int ui[MAXN],vi[MAXN],vall[MAXN];
inline void add_edge(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
nxt[cnt]=head[v];
head[v]=cnt;
}
int dep[MAXN],fat[MAXN],siz[MAXN],son[MAXN];
int dfn[MAXN],/*end[MAXN],*/top[MAXN];
void dfs1(int u,int f){
u[dep]=f[dep]+1;
u[fat]=f;
u[siz]=1;
u[son]=0;
for(int i=u[head],v;i;i=i[nxt])
if((v=to[i])!=f){
dfs1(v,u);
u[siz]+=v[siz];
if(v[siz]>siz[son[u]])u[son]=v;
}
}
void dfs2(int u,int f){
u[dfn]=++tim;
u[top]=(u==f[son])?f[top]:u;
if(u[son])dfs2(u[son],u);
for(int i=u[head],v;i;i=i[nxt])
if((v=i[to])!=f&&v!=u[son])dfs2(v,u);
//u[end]=cnt;
}
//int a[MAXN];
int mm[MAXN<<2];
inline void push_up(int rt){mm[rt]=max(mm[rt<<1],mm[rt<<1|1]);}
/*void build(int l,int r,int rt){
if(l==r){mm[rt]=a[l];return;}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
push_up(rt);
}*/
void update(int pos,int vl,int l,int r,int rt){
if(pos<l||pos>r)return;
if(pos==l&&pos==r){mm[rt]=vl;return;}
int mid=(l+r)>>1;
if(pos<=mid)update(pos,vl,l,mid,rt<<1);
else update(pos,vl,mid+1,r,rt<<1|1);
push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L>R||r<L||l>R)return 0;
if(L<=l&&r<=R)return mm[rt];
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)ans=max(ans,query(L,R,l,mid,rt<<1));
if(mid<R)ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
return ans;
}
int get_ans(int x,int y){
int rs=0;
for(int ta=top[x],tb=top[y];ta!=tb;)
if(dep[ta]>dep[tb])
rs=max(rs,query(dfn[ta],dfn[x],1,n,1)),ta=top[x=fat[ta]];
else
rs=max(rs,query(dfn[tb],dfn[y],1,n,1)),tb=top[y=fat[tb]];
if(dep[x]>dep[y])swap(x,y);
return max(rs,query(dfn[x]+1,dfn[y],1,n,1));
}
int val[MAXN];
int main(){
memset(head,0,sizeof(head));
memset(dep,0,sizeof(dep));
memset(siz,0,sizeof(siz));
memset(son,0,sizeof(son));
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d%d",ui+i,vi+i,vall+i);
add_edge(i[ui],i[vi]);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<n;i++){//边权改点权
if(dep[ui[i]]>dep[vi[i]])swap(ui[i],vi[i]);
val[vi[i]]=vall[i];
}
/*memset(a,0,sizeof(a));
for(int i=1;i<n;i++)
if(i[ui][dep]<i[vi][dep])a[i[vi][dfn]]=i[val];
else a[i[ui][dfn]]=i[val];*/
memset(mm,0,sizeof(mm));
//build(1,n,1);
for(int i=1;i<=n;i++)update(dfn[i],val[i],1,n,1);
static char s[10];
while(scanf("%s",s),s[0]!='D'){
int x,y;
scanf("%d%d",&x,&y);
if(s[0]=='Q'){
printf("%d\n",get_ans(x,y));
}else{
update(dfn[vi[x]],y,1,n,1);
}
}
return 0;
}版权声明：本文是原创文章，版权归 无限UCW 所有。
本文链接：https://ucw.moe/archives/solution-luogu-p4114.html
本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。
