边权树链剖分
一般的树链剖分都是维护的点权,而如果要维护边权怎么办呢?
思路
我们可以把边权转换为点权。一个点有很多个儿子,但只有一个父亲。如果一个节点的点权记录到其儿子的边权就显然不行了,只能记录这个点到其父亲的边权。
如果要修改查询 \(\text{x---y}\) 的所有边权,通过维护点权的思路,先修改查询 \(\text{x---lca(x,y)}\) 再修改查询 \(\text{lca(x,y)---y}\) ,但这样会出现一个问题。
像上面这张图,如果要修改查询 \(\text{4---6}\) ,应先从 \(\text{4---3}\) ,再从 \(\text{3---6}\)。但我们发现点 \(\text{3}\) 存储的点权是 \(\text{3---1}\) 的边权,不属于要修改查询的,不应该修改。所以我们应该对点权树剖的代码做一下改动。
tree.change(1,dfn[y],dfn[x],z);
tree.change(1,dfn[y]+1,dfn[x],z);
这样就能避免上述情况了。剩下的操作都和点权树剖一样。
题目
这个题就是边权树剖的模板,不过有一个坑点,就是要注意push_up/push_down
的时候要清空各种标记。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int ver[MAXN<<1],nxt[MAXN<<1],head[MAXN],edge[MAXN<<1],a[MAXN],tot,n;
int fa[MAXN],de[MAXN],dfn[MAXN],fdfn[MAXN],top[MAXN],son[MAXN],siz[MAXN],cnt;
int eg[MAXN][2];
void add(int x,int y,int z){
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
edge[tot]=z;
}
void dfs1(int x,int f,int e){//处理各种数组
fa[x]=f,de[x]=de[fa[x]]+1,a[x]=e,siz[x]=1;//a[x]=e:把点权设成这个点到父亲的边权
for(int i=head[x];i;i=nxt[i]){//板子
if(ver[i]==fa[x])continue;
dfs1(ver[i],x,edge[i]);
siz[x]+=siz[ver[i]];
if(siz[ver[i]]>siz[son[x]])son[x]=ver[i];
}
}
void dfs2(int x,int f){//板子
top[x]=f,dfn[x]=++cnt,fdfn[cnt]=x;
if(!son[x])return;
dfs2(son[x],f);
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==fa[x])continue;
if(ver[i]==son[x])continue;
dfs2(ver[i],ver[i]);
}
}
struct SegmentTree{//板子
const int NO_CHANGE=-0x7fffffff;
struct node{
int l,r,maxn,cov,add;
}t[MAXN<<2];
#define LSON (p<<1)
#define RSON ((p<<1)|1)
#define mid ((l+r)>>1)
void make_lazy_tag_cov(int p,int val){
t[p].add=0;//赋值时应当清空加法标记
t[p].maxn=val;
t[p].cov=val;
}
void make_lazy_tag_add(int p,int val){
t[p].maxn+=val;//加法时不用清空赋值标记
t[p].add+=val;
}
void push_up(int p){
t[p].maxn=max(t[LSON].maxn,t[RSON].maxn);
}
void push_down(int p){//QAQ,线段树都敲烂了,还是错了push_down.
if(t[p].cov!=NO_CHANGE){//下传赋值标记
make_lazy_tag_cov(LSON,t[p].cov);
make_lazy_tag_cov(RSON,t[p].cov);
t[p].cov=NO_CHANGE;
}
if(t[p].add){//下穿加法标记
make_lazy_tag_add(LSON,t[p].add);
make_lazy_tag_add(RSON,t[p].add);
t[p].add=0;
}
}
void build(int p,int l,int r){//板子
if(l>r)return;
t[p].l=l,t[p].r=r,t[p].add=0,t[p].cov=NO_CHANGE;
if(l==r){
t[p].maxn=a[fdfn[l]];
return;
}
build(LSON,l,mid);
build(RSON,mid+1,r);
push_up(p);
}
void change_cov(int p,int l,int r,int val){//板子
if(l>r)return;
if(l<=t[p].l&&t[p].r<=r){
make_lazy_tag_cov(p,val);
return;
}
push_down(p);
if(t[LSON].r>=l)change_cov(LSON,l,r,val);
if(t[RSON].l<=r)change_cov(RSON,l,r,val);
push_up(p);
}
void change_add(int p,int l,int r,int val){//板子
if(l>r)return;
if(l<=t[p].l&&t[p].r<=r){
make_lazy_tag_add(p,val);
return;
}
push_down(p);
if(t[LSON].r>=l)change_add(LSON,l,r,val);
if(t[RSON].l<=r)change_add(RSON,l,r,val);
push_up(p);
}
int ask_max(int p,int l,int r){//板子
if(l>r)return -0x7fffffff;
if(l<=t[p].l&&t[p].r<=r)return t[p].maxn;
push_down(p);
int ans=-0x7fffffff;
if(t[LSON].r>=l)ans=max(ans,ask_max(LSON,l,r));
if(t[RSON].l<=r)ans=max(ans,ask_max(RSON,l,r));
return ans;
}
}tree;
void cover_u_to_v(int u,int v,int w){
while(top[u]!=top[v]){//板子
if(de[top[u]]<de[top[v]])swap(u,v);
tree.change_cov(1,dfn[top[u]],dfn[u],w);
u=fa[top[u]];
}
if(de[u]<de[v])swap(u,v);
tree.change_cov(1,dfn[v]+1,dfn[u],w);//与点权树剖不一样的地方
}
void add_u_to_v(int u,int v,int w){
while(top[u]!=top[v]){//板子
if(de[top[u]]<de[top[v]])swap(u,v);
tree.change_add(1,dfn[top[u]],dfn[u],w);
u=fa[top[u]];
}
if(de[u]<de[v])swap(u,v);
tree.change_add(1,dfn[v]+1,dfn[u],w);//与点权树剖不一样的地方
}
int ask_max_u_to_v(int u,int v){
int ans=-0x7fffffff;
while(top[u]!=top[v]){//板子
if(de[top[u]]<de[top[v]])swap(u,v);
ans=max(ans,tree.ask_max(1,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(de[u]<de[v])swap(u,v);
ans=max(ans,tree.ask_max(1,dfn[v]+1,dfn[u]));//与点权树剖不一样的地方
return ans;
}
int main(){
cin>>n;
for(int i=1,w;i<n;i++){
cin>>eg[i][0]>>eg[i][1]>>w;
add(eg[i][0],eg[i][1],w);
add(eg[i][1],eg[i][0],w);
}
fa[1]=de[1]=1;
dfs1(1,1,0);
dfs2(1,1);
tree.build(1,1,n);
string op;
for(int i=1,u,v,w;;i++){
cin>>op;
if(op=="Stop")break;
if(op=="Max"){
cin>>u>>v;
cout<<ask_max_u_to_v(u,v)<<endl;
}
if(op=="Cover"){
cin>>u>>v>>w;
cover_u_to_v(u,v,w);
}
if(op=="Add"){
cin>>u>>v>>w;
add_u_to_v(u,v,w);
}
if(op=="Change"){
cin>>u>>w;
cover_u_to_v(eg[u][0],eg[u][1],w);
}
}
return 0;
}
标签:val,剖分,cov,int,text,边权,树链,add
From: https://www.cnblogs.com/maniubi/p/16986073.html