【博客】树链剖分瞎入门
本文旨在让读者背代码
这绝对是全网最长的树剖文章
前言
在做题时，我们可能会遇到这样一类问题：
给定一棵
个结点的树和
次操作，操作有两种，一种是给定两个结点，让连接两个结点的路径上的所有点权值加上一个值，另一种是查询路径上所有点的权值和。
，
。
如果是最后统一输出结点权值，用树上差分+dfs 就能轻松水过，而对于在线查询，如果数据范围小的话暴力即可 AC，时间复杂度 ，但是很明显，这个数据范围肯定不能这么写了。此时，就需要树链剖分出场了。
树链剖分
原理
树链剖分是根据轻重儿子，将一棵树剖成多条链，然后就可以用数据结构来维护这些链了，听着似乎还是有点像暴力，不过因为一条链有多个结点，所以可以优化时间复杂度。
至于轻重儿子的定义，请见下一块。
实现
既然要把树剖成一堆链，那么我们就要有一种标准来剖这棵树，树链剖分的标准是什么呢？我们定义：一个结点的所有子树中，结点数最多的子树的根节点是这个结点的“重儿子”，比如下面这张图中，红点就是蓝点的重儿子。
递归进行这个过程，我们可以得到一堆的“重儿子”，将这些重儿子连起来，我们就会得到一根“重链”，最后对整棵树完成这个过程后，我们就将一棵树剖成了若干个“重链”。
剖完之后，还有一些点，它们则称为“轻儿子”，一些轻边连成的链则称为轻链。（然而这个并没有什么卵用）
此时我们已经剖完了树，我们就要考虑怎么维护这些链了。在说怎么维护之前，我们先把怎么剖用代码的方式表示出来。
对于树链剖分，我们需要维护以下的数组：
| 名称 | 含义 |
|---|---|
| 以 | |
注：每个轻儿子的 就是它本身。
首先，因为我们在 dfs 时应该先往重儿子搜索，所以一个 dfs 肯定是不能完成任务，所以我们需要两个 dfs 函数。
这两个 dfs 函数分别完成什么呢？
：预处理
，
，
，
数组。
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
dep[v]=dep[u]+1;
faz[v]=u;
Dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}：预处理
，
，
数组。其中
数组有的时候用不到，在部分题目中可以省略。
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
rk[Index]=u;
top[u]=rt;
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}注意点： 没有什么好注意的，
的时候记得先往重儿子搜，至于为什么？
维护链
dfs 序
首先讲一下，为什么要先搜重儿子。因为我们要维护的是重链，而一条链的要求必须是连续的，而我们维护时使用数据结构，必然是要将它转换到数列上来做的，如何转换呢？最好的方法就是按照 dfs 序，此时如果不先搜重儿子的话，重链上的 dfs 序就可能会断掉，如下图（橙、绿线是 dfs 搜索顺序）：
这条链的 dfs 序就断开了，此时就无法用数据结构去维护了。
如何维护
这一节很简单，没什么好讲的，因为要维护的是链，而且我们现在已经保证链上的 dfs 序连续了，所以我们直接取结点的 到它自己这一段进行修改或查询（即使用 dfs 序修改），然后再将当前结点跳到它
的
即可。为了防止一个结点无限往上跳，我们先选
比较深的那个结点进行修改/查询，再往上跳，就可以防止无限跳的情况了。而如果选的是浅的，而它又往上跳，则深度越来越浅，必然会无限跳，最终死循环。
最后，这两个结点一定会到一条链上，而且必然有一个点会是 LCA，我们最后进行一次操作即可。
至于为什么是跳到 的
，因为
已经被修改/查询过了，跳到上一个结点防止重复操作。
修改：
void ModifyOnTree(int u,int v,int val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
Modify(1,1,n,dfn[top[u]],dfn[u],val);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
Modify(1,1,n,dfn[u],dfn[v],val);
}查询（根据求和、求最小值、求最大值修改，仅给出求和）：
int QueryOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=Query(1,1,n,dfn[top[u]],dfn[u]);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=Query(1,1,n,dfn[u],dfn[v]);
return res;
}至于其中的 和
函数，根据不同的需求和使用的数据结构的不同，应自行修改。
例题
P3384 【模板】树链剖分
操作涉及区间加、区间和、子树加、子树和，区间的两种操作直接用线段树配合上面的模板可以轻松过去，而子树加和子树和这两个新操作呢？其实更简单。我们知道，一个子树的 dfs 序必然是连续的，所以我们直接对 到
这个序列进行区间加、区间和的操作即可，使用线段树即可无脑水过。
代码因为年代久远，码风太丑，不贴了。
重要注意点：子树操作在 传
的时候，对
的加需要乘上区间长度的一半，和普通线段树一样，切记。
P2590 [ZJOI2008]树的统计
操作涉及单点修改、区间最大值、区间和，无脑水过。
#include<bits/stdc++.h>
#define MAXN 100005
#define inf 2147400000
using namespace std;
int cnt,fst[MAXN],nxt[MAXN],to[MAXN];
int n,Q,a[MAXN>>1],Index,sum[MAXN<<2],maxn[MAXN<<2];
int siz[MAXN],son[MAXN],faz[MAXN],dep[MAXN],top[MAXN],rk[MAXN],id[MAXN];
void AddEdge(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
}
void Dfs1(int u,int fa)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
dep[v]=dep[u]+1;
faz[v]=u;
Dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
id[u]=++Index;
rk[Index]=u;
top[u]=rt;
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
}
void BuildSegmentTree(int rt,int l,int r)
{
if(l==r)
{
sum[rt]=maxn[rt]=a[rk[l]];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void Modify(int rt,int l,int r,int pos,int val)
{
if(l==r)
{
sum[rt]=maxn[rt]=val;
return;
}
int mid=l+r>>1;
if(pos<=mid) Modify(rt<<1,l,mid,pos,val);
else Modify(rt<<1|1,mid+1,r,pos,val);
PushUp(rt);
}
int QuerySum(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return sum[rt];
int mid=l+r>>1,res=0;
if(tl<=mid) res+=QuerySum(rt<<1,l,mid,tl,tr);
if(tr>mid) res+=QuerySum(rt<<1|1,mid+1,r,tl,tr);
PushUp(rt);
return res;
}
int QueryMaxn(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return maxn[rt];
int mid=l+r>>1,res=-inf;
if(tl<=mid) res=max(res,QueryMaxn(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,QueryMaxn(rt<<1|1,mid+1,r,tl,tr));
PushUp(rt);
return res;
}
int QuerySumOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=QuerySum(1,1,n,id[top[u]],id[u]);
u=faz[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
res+=QuerySum(1,1,n,id[v],id[u]);
return res;
}
int QueryMaxOnTree(int u,int v)
{
int res=-inf;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=max(res,QueryMaxn(1,1,n,id[top[u]],id[u]));
u=faz[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
res=max(res,QueryMaxn(1,1,n,id[v],id[u]));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
AddEdge(x,y);
AddEdge(y,x);
}
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dep[1]=1;
faz[1]=1;
Dfs1(1,0);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
scanf("%d",&Q);
while(Q--)
{
int x,y;
string opt;
cin>>opt>>x>>y;
if(opt=="CHANGE") Modify(1,1,n,id[x],y);
else if(opt=="QMAX") printf("%d\n",QueryMaxOnTree(x,y));
else if(opt=="QSUM") printf("%d\n",QuerySumOnTree(x,y));
}
return 0;
}P3178 [HAOI2015]树上操作
操作涉及单点加、子树加、区间和，依然无脑水过。
#include<bits/stdc++.h>
#define MAXN 100005
#define ll long long
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1];
int n,Q;
int dfn[MAXN],Index,top[MAXN],faz[MAXN],dep[MAXN],siz[MAXN],son[MAXN];
ll t[MAXN<<2],tag[MAXN<<2],rk[MAXN],a[MAXN];
void AddEdge(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
dep[v]=dep[u]+1;
faz[v]=u;
Dfs1(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
rk[Index]=a[u];
top[u]=rt;
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
t[rt]=t[rt<<1]+t[rt<<1|1];
}
void PushDown(int rt,ll len)
{
if(tag[rt])
{
tag[rt<<1]+=tag[rt];
tag[rt<<1|1]+=tag[rt];
t[rt<<1]+=tag[rt]*(len-(len>>1));
t[rt<<1|1]+=tag[rt]*(len>>1);
tag[rt]=0;
}
}
void BuildSegmentTree(int rt,int l,int r)
{
if(l==r)
{
t[rt]=rk[l];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void Modify(int rt,int l,int r,int tl,int tr,ll val)
{
if(tl<=l && r<=tr)
{
tag[rt]+=val;
t[rt]+=1ll*val*(r-l+1);
return;
}
PushDown(rt,r-l+1);
int mid=l+r>>1;
if(tl<=mid) Modify(rt<<1,l,mid,tl,tr,val);
if(tr>mid) Modify(rt<<1|1,mid+1,r,tl,tr,val);
PushUp(rt);
}
ll Query(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
PushDown(rt,r-l+1);
int mid=l+r>>1;
ll res=0;
if(tl<=mid) res+=Query(rt<<1,l,mid,tl,tr);
if(tr>mid) res+=Query(rt<<1|1,mid+1,r,tl,tr);
return res;
}
ll QueryOnTree(int u,int v)
{
ll res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=Query(1,1,n,dfn[top[u]],dfn[u]);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=Query(1,1,n,dfn[u],dfn[v]);
return res;
}
int main()
{
scanf("%d %d",&n,&Q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
while(Q--)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
int x,y;
scanf("%d %d",&x,&y);
Modify(1,1,n,dfn[x],dfn[x],y);
}
else if(opt==2)
{
int x,y;
scanf("%d %d",&x,&y);
Modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,y);
}
else
{
int x;
scanf("%d",&x);
printf("%lld\n",QueryOnTree(1,x));
}
}
return 0;
}P4315 月下“毛景树”
操作涉及单点覆盖、区间覆盖、区间加、区间最大值，本来应该是无脑水过，但是因为要将边权转成点权，然后忽略掉 ，还是有点难度，具体解析见：题解 P4315 【月下“毛景树”】
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],w[MAXN<<1],fr[MAXN<<1];
int n,a[MAXN],t[MAXN<<2],tag[MAXN<<2],cov[MAXN<<2];
int siz[MAXN],son[MAXN],dfn[MAXN],Index,top[MAXN],rk[MAXN],dep[MAXN],faz[MAXN];
string s;
void AddEdge(int u,int v,int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
fr[cnt]=u;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
faz[v]=u;
dep[v]=dep[u]+1;
rk[v]=w[i];
Dfs1(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
top[u]=rt;
a[Index]=rk[u];
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void PushDown(int rt)
{
if(~cov[rt])
{
cov[rt<<1]=cov[rt<<1|1]=cov[rt];
t[rt<<1]=t[rt<<1|1]=cov[rt];
tag[rt<<1]=tag[rt<<1|1]=0;
cov[rt]=-1;
}
tag[rt<<1]+=tag[rt];
tag[rt<<1|1]+=tag[rt];
t[rt<<1]+=tag[rt];
t[rt<<1|1]+=tag[rt];
tag[rt]=0;
}
void BuildSegmentTree(int rt,int l,int r)
{
cov[rt]=-1;
if(l==r)
{
t[rt]=a[l];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void ModifyCover(int rt,int l,int r,int tl,int tr,int val)
{
if(tl<=l && r<=tr)
{
t[rt]=cov[rt]=val;
tag[rt]=0;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(tl<=mid) ModifyCover(rt<<1,l,mid,tl,tr,val);
if(tr>mid) ModifyCover(rt<<1|1,mid+1,r,tl,tr,val);
PushUp(rt);
}
void ModifyAdd(int rt,int l,int r,int tl,int tr,int val)
{
if(tl<=l && r<=tr)
{
t[rt]+=val;
tag[rt]+=val;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(tl<=mid) ModifyAdd(rt<<1,l,mid,tl,tr,val);
if(tr>mid) ModifyAdd(rt<<1|1,mid+1,r,tl,tr,val);
PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
PushDown(rt);
int mid=l+r>>1,res=0;
if(tl<=mid) res=max(res,Query(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,Query(rt<<1|1,mid+1,r,tl,tr));
return res;
}
void ModifyCoverOnTree(int u,int v,int val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ModifyCover(1,1,n,dfn[top[u]],dfn[u],val);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ModifyCover(1,1,n,dfn[u]+1,dfn[v],val);
}
void ModifyAddOnTree(int u,int v,int val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ModifyAdd(1,1,n,dfn[top[u]],dfn[u],val);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ModifyAdd(1,1,n,dfn[u]+1,dfn[v],val);
}
int QueryMaxnOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=max(res,Query(1,1,n,dfn[top[u]],dfn[u]));
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res=max(res,Query(1,1,n,dfn[u]+1,dfn[v]));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
while(1)
{
int x,y,z;
cin>>s;
if(s=="Stop") break;
else
{
scanf("%d %d",&x,&y);
if(s=="Change")
{
x<<=1;
int u=fr[x],v=to[x];
if(dep[u]>dep[v]) swap(u,v);
ModifyCoverOnTree(u,v,y);
}
else if(s=="Cover")
{
scanf("%d",&z);
ModifyCoverOnTree(x,y,z);
}
else if(s=="Add")
{
scanf("%d",&z);
ModifyAddOnTree(x,y,z);
}
else if(s=="Max") printf("%d\n",QueryMaxnOnTree(x,y));
}
}
return 0;
}P4114 Qtree1
和上一题一样，边权转点权，无脑操作即可。
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],w[MAXN<<1];
int n,a[MAXN],t[MAXN<<2],fr[MAXN],tx[MAXN];
int dfn[MAXN],Index,faz[MAXN],siz[MAXN],son[MAXN],dep[MAXN],top[MAXN],rk[MAXN];
char ch[15];
void AddEdge(int u,int v,int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
dep[v]=dep[u]+1;
faz[v]=u;
a[v]=w[i];
Dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
rk[Index]=u;
top[u]=rt;
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void BuildSegmentTree(int rt,int l,int r)
{
if(l==r)
{
t[rt]=a[rk[l]];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void Modify(int rt,int l,int r,int pos,int val)
{
if(l==r)
{
t[rt]=val;
return;
}
int mid=l+r>>1;
if(pos<=mid) Modify(rt<<1,l,mid,pos,val);
else Modify(rt<<1|1,mid+1,r,pos,val);
PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
int mid=l+r>>1;
int res=0;
if(tl<=mid) res=max(res,Query(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,Query(rt<<1|1,mid+1,r,tl,tr));
return res;
}
int QueryOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=max(res,Query(1,1,n,dfn[top[u]],dfn[u]));
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res=max(res,Query(1,1,n,dfn[u]+1,dfn[v]));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
int z;
scanf("%d %d %intd",&x,&y,&z);
fr[i]=x;
tx[i]=y;
AddEdge(x,y,z);
AddEdge(y,x,z);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
while(1)
{
scanf("%s",ch+1);
if(ch[1]=='D') break;
else
{
int x,y;
scanf("%d %d",&x,&y);
if(ch[1]=='Q') printf("%d\n",QueryOnTree(x,y));
else
{
int t=dep[fr[x]]>dep[tx[x]]?fr[x]:tx[x];
Modify(1,1,n,dfn[t],y);
}
}
}
return 0;
}P1505 [国家集训队]旅游
最后一道，来道毒瘤的，操作涉及单点修改，区间取相反数，区间和，区间最大值，区间最小值，其他的都简单，就是区间取相反数较难，我们在取相反时，将最大值和最小值**交换**，然后将和、最大值、最小值全部乘上 就行，码量较大，耐心码耐心调还是可以比较轻松的
掉的。
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],w[MAXN<<1];
int n,Q,a[MAXN],t[MAXN<<2],tag[MAXN<<2],maxn[MAXN<<2],minx[MAXN<<2];
int siz[MAXN],son[MAXN],top[MAXN],dep[MAXN],faz[MAXN],dfn[MAXN],Index,rk[MAXN];
string s;
void AddEdge(int u,int v,int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
dep[v]=dep[u]+1;
faz[v]=u;
rk[v]=w[i];
Dfs1(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
top[u]=rt;
dfn[u]=++Index;
a[Index]=rk[u];
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
void PushUp(int rt)
{
t[rt]=t[rt<<1]+t[rt<<1|1];
maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
minx[rt]=min(minx[rt<<1],minx[rt<<1|1]);
}
void PushDown(int rt)
{
if(tag[rt])
{
t[rt<<1]*=-1;
t[rt<<1|1]*=-1;
tag[rt<<1]^=1;
tag[rt<<1|1]^=1;
swap(maxn[rt<<1],minx[rt<<1]);
swap(maxn[rt<<1|1],minx[rt<<1|1]);
maxn[rt<<1]*=-1;
minx[rt<<1]*=-1;
maxn[rt<<1|1]*=-1;
minx[rt<<1|1]*=-1;
tag[rt]=0;
}
}
void BuildSegmentTree(int rt,int l,int r)
{
if(l==r)
{
t[rt]=maxn[rt]=minx[rt]=a[l];
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
PushUp(rt);
}
void ModifyPoint(int rt,int l,int r,int pos,int val)
{
if(l==r)
{
t[rt]=maxn[rt]=minx[rt]=val;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(pos<=mid) ModifyPoint(rt<<1,l,mid,pos,val);
else ModifyPoint(rt<<1|1,mid+1,r,pos,val);
PushUp(rt);
}
void ModifyNega(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr)
{
t[rt]*=-1;
tag[rt]^=1;
swap(maxn[rt],minx[rt]);
maxn[rt]*=-1;
minx[rt]*=-1;
return;
}
PushDown(rt);
int mid=l+r>>1;
if(tl<=mid) ModifyNega(rt<<1,l,mid,tl,tr);
if(tr>mid) ModifyNega(rt<<1|1,mid+1,r,tl,tr);
PushUp(rt);
}
int QuerySum(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
PushDown(rt);
int mid=l+r>>1,res=0;
if(tl<=mid) res+=QuerySum(rt<<1,l,mid,tl,tr);
if(tr>mid) res+=QuerySum(rt<<1|1,mid+1,r,tl,tr);
return res;
}
int QueryMaxn(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return maxn[rt];
PushDown(rt);
int mid=l+r>>1,res=-2e9;
if(tl<=mid) res=max(res,QueryMaxn(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,QueryMaxn(rt<<1|1,mid+1,r,tl,tr));
return res;
}
int QueryMinx(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return minx[rt];
PushDown(rt);
int mid=l+r>>1,res=2e9;
if(tl<=mid) res=min(res,QueryMinx(rt<<1,l,mid,tl,tr));
if(tr>mid) res=min(res,QueryMinx(rt<<1|1,mid+1,r,tl,tr));
return res;
}
void ModifyToNegative(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ModifyNega(1,1,n,dfn[top[u]],dfn[u]);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ModifyNega(1,1,n,dfn[u]+1,dfn[v]);
}
int QuerySumOnTree(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=QuerySum(1,1,n,dfn[top[u]],dfn[u]);
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=QuerySum(1,1,n,dfn[u]+1,dfn[v]);
return res;
}
int QueryMaxnOnTree(int u,int v)
{
int res=-2e9;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=max(res,QueryMaxn(1,1,n,dfn[top[u]],dfn[u]));
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res=max(res,QueryMaxn(1,1,n,dfn[u]+1,dfn[v]));
return res;
}
int QueryMinxOnTree(int u,int v)
{
int res=2e9;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res=min(res,QueryMinx(1,1,n,dfn[top[u]],dfn[u]));
u=faz[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res=min(res,QueryMinx(1,1,n,dfn[u]+1,dfn[v]));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
AddEdge(x+1,y+1,z);
AddEdge(y+1,x+1,z);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
scanf("%d",&Q);
while(Q--)
{
cin>>s;
int x,y;
scanf("%d %d",&x,&y);
if(s=="C") ModifyPoint(1,1,n,dfn[x+1],y);
else if(s=="N") ModifyToNegative(x+1,y+1);
else if(s=="SUM") printf("%d\n",QuerySumOnTree(x+1,y+1));
else if(s=="MAX") printf("%d\n",QueryMaxnOnTree(x+1,y+1));
else if(s=="MIN") printf("%d\n",QueryMinxOnTree(x+1,y+1));
}
return 0;
}P3613 睡觉困难综合征
这道题是真的难了，首先观察原版 [P2114 [NOI2014]起床困难综合症](https://www.luogu.org/problemnew/show/P2114) 的做法，用一个每一个二进制位都是 数（即
）和一个每一个二进制位都是
的数（即
）跑一遍，然后从高位贪心选，这道题的核心思想也是这样的，线段树记录的是每一段路径上，
和
分别从左往右跑和从右往左跑最终的结果。显然，我们每一个二进制位都要维护一个值，这样的时间复杂度显然是
，即树链剖分的时间复杂度乘上每次计算二进制位的结果的时间复杂度，虽然看着不大，但是因为有一个
，以及时限只有
，而且出题人又是那个谁谁谁，这个复杂度就算是卡常也过不去，此时我们就要想办法优化了。
观察时间复杂度， 是树剖的基础时间复杂度，怎么优化都是优化不掉的，我们考虑优化掉那个
，我们现在算结果是一位一位算的，所以是
，那么有没有方法在
的时间复杂度内就把结果算出来呢？其实是有的
，只是我不会证，看不懂。
总而言之就是：
其中 是当前结点，
是左儿子，
是右儿子，
是类型，即从左往右或从右往左，当然，在计算从右往左的时候要把 **所有
和
反过来**，毕竟是反的嘛。
按照这个式子，我们可以写出一个计算的函数，然后就可以建线段树了。当然，事情还没有完，因为在树上查询的时候，我们原来是两边交替往上跳，但是因为这道题，方向不同结果也不同，比如 这条路径，一般走法应该是
，
，但是在平时树剖的过程中，就可能是
，
，一般是没有影响的，但是这题涉及了位运算，操作乱序结果显然会不同，所以我们要分别跳，对于不同的情况存在两个不同的序列里，然后最后把其中一个序列的从左往右从右往左交换一下，最后再做位运算跑贪心。
记得开 unsigned long long。
#include<bits/stdc++.h>
#define MAXN 200005
#define ull unsigned long long
using namespace std;
const ull MAXULL=-1;
struct Node
{
ull l0,l1,r0,r1;
}t[MAXN<<2],ans1[MAXN],ans2[MAXN];
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1];
int n,Q,K,opt[MAXN],tot1,tot2;
int siz[MAXN],son[MAXN],dfn[MAXN],Index,dep[MAXN],faz[MAXN],top[MAXN],rk[MAXN];
ull a[MAXN];
template <typename T> void Read(T &x)
{
int fu=1;
x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fu=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch-48);
x*=fu;
}
void AddEdge(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
}
void Dfs1(int u)
{
siz[u]=1;
son[u]=0;
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u]) continue;
faz[v]=u;
dep[v]=dep[u]+1;
Dfs1(v);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void Dfs2(int u,int rt)
{
dfn[u]=++Index;
rk[Index]=u;
top[u]=rt;
if(son[u]) Dfs2(son[u],rt);
for(int i=fst[u];i;i=nxt[i])
{
int v=to[i];
if(v==faz[u] || v==son[u]) continue;
Dfs2(v,v);
}
}
ull Calc(ull x,int rt)
{
return opt[rt]==1?x&a[rt]:(opt[rt]==2?x|a[rt]:x^a[rt]);
}
Node CalcNode(Node x,Node y)
{
Node res;
res.l0=((x.l0&y.l1)|(((~x.l0)&y.l0)));
res.l1=((x.l1&y.l1)|(((~x.l1)&y.l0)));
res.r0=((y.r0&x.r1)|(((~y.r0)&x.r0)));
res.r1=((y.r1&x.r1)|(((~y.r1)&x.r0)));
return res;
}
void BuildSegmentTree(int rt,int l,int r)
{
if(l==r)
{
t[rt].l0=t[rt].r0=Calc(0,rk[l]);
t[rt].l1=t[rt].r1=Calc(MAXULL,rk[l]);
return;
}
int mid=l+r>>1;
BuildSegmentTree(rt<<1,l,mid);
BuildSegmentTree(rt<<1|1,mid+1,r);
t[rt]=CalcNode(t[rt<<1],t[rt<<1|1]);
}
void Modify(int rt,int l,int r,int pos)
{
if(l==r)
{
t[rt].l0=t[rt].r0=Calc(0,rk[l]);
t[rt].l1=t[rt].r1=Calc(MAXULL,rk[l]);
return;
}
int mid=l+r>>1;
if(mid>=pos) Modify(rt<<1,l,mid,pos);
else Modify(rt<<1|1,mid+1,r,pos);
t[rt]=CalcNode(t[rt<<1],t[rt<<1|1]);
}
Node Query(int rt,int l,int r,int tl,int tr)
{
if(tl<=l && r<=tr) return t[rt];
int mid=l+r>>1;
Node res;
if(tr<=mid) res=Query(rt<<1,l,mid,tl,tr);
else if(tl>mid) res=Query(rt<<1|1,mid+1,r,tl,tr);
else res=CalcNode(Query(rt<<1,l,mid,tl,tr),Query(rt<<1|1,mid+1,r,tl,tr));
return res;
}
Node QueryOnTree(int u,int v)
{
Node res;
tot1=tot2=0;
while(top[u]!=top[v])
{
if(dep[top[u]]>=dep[top[v]])
{
ans1[++tot1]=Query(1,1,n,dfn[top[u]],dfn[u]);
u=faz[top[u]];
}
else
{
ans2[++tot2]=Query(1,1,n,dfn[top[v]],dfn[v]);
v=faz[top[v]];
}
}
if(dep[u]>dep[v]) ans1[++tot1]=Query(1,1,n,dfn[v],dfn[u]);
else ans2[++tot2]=Query(1,1,n,dfn[u],dfn[v]);
for(int i=1;i<=tot1;i++)
{
swap(ans1[i].l0,ans1[i].r0);
swap(ans1[i].l1,ans1[i].r1);
}
if(tot1)
{
res=ans1[1];
for(int i=2;i<=tot1;i++) res=CalcNode(res,ans1[i]);
if(tot2) res=CalcNode(res,ans2[tot2]);
}
else res=ans2[tot2];
for(int i=tot2-1;i>=1;i--) res=CalcNode(res,ans2[i]);
return res;
}
int main()
{
Read(n);
Read(Q);
Read(K);
for(int i=1;i<=n;i++)
{
Read(opt[i]);
Read(a[i]);
}
for(int i=1;i<n;i++)
{
int x,y;
Read(x);
Read(y);
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1);
Dfs2(1,1);
BuildSegmentTree(1,1,n);
while(Q--)
{
int Opt;
ull x,y,z;
Read(Opt);
Read(x);
Read(y);
Read(z);
if(Opt==1)
{
Node res=QueryOnTree(x,y);
ull ans=0;
for(int i=63;i>=0;i--)
{
ull l=(res.l0>>i)&1ull,r=(res.l1>>i)&1ull;
if(l>=r || (1ull<<i)>z)
{
if(l) ans|=(1ull<<i);
}
else
{
if(r) ans|=(1ull<<i);
z-=(1ull<<i);
}
}
printf("%llu\n",ans);
}
else if(Opt==2)
{
opt[x]=y;
a[x]=z;
Modify(1,1,n,dfn[x]);
}
}
return 0;
}总结
无。
京东二面144人在聊
查看8道真题和解析