题目大意
对一颗树进行两种操作:将一条从 \(u\) 到 \(v\) 的链上的点的权值增加 \(x\);查询从 \(u\) 到 \(v\) 的链上最大的 \(p_i-p_j(dis_{ui}<dis_{uj})\),其中 \(p_i\) 表示点 \(i\) 的权值,\(dis_{AB}\) 表示点 \(A,B\) 间唯一路径上边的数量。
思路分析
先思考,如果没有 \(dis_{ui}<dis_{uj}\) 这个条件,那么这个问题将十分简单,我们只需要用线段树维护链上的最大值,最小值,实现区间加操作即可。
但是多了这个限制条件,我们的做法就要做出一些改变。
首先,我们可以发现,这个条件是有方向性的。也就是说,对于一对查询的 \(u,v\),如果将 \(u,v\) 交换,查询的结果可能会发生变化,这与我们熟知的链上的和,最大值,最小值之类的是不同的。
那么我们可以先将问题简化,将树上问题变成序列问题。
在序列上维护这样一种带有方向性的可合并的信息,我们最常用的方法就是线段树,而线段树维护的核心就是区间合并,所以我们先思考区间合并如何实现。
容易发现,其实我们只需要维护区间的最大值 \(\text{max}\),最小值 \(\text{min}\),从左向右的最大差值 \(\text{atob}\),从右向左的最大差值 \(\text{btoa}\)(十分形象)就可以解决这个问题,具体的维护方法如下:
a.max=max(ls.max,rs.max);
a.min=min(ls.min,rs.min);
a.atob=max(max(ls.atob,rs.atob),ls.max-rs.min);
a.btoa=max(max(ls.btoa,rs.btoa),rs.max-ls.min);
剩下的线段树部分十分套路,想必大家都会写。(区间加,区间查询某个属性)
那么,我们现在既然有了序列上问题的做法,剩下的就只有把这个做法扩展到树上了。
对于一颗静态树上的链的维护和查询,最常用的方法无疑是树链剖分,树链剖分的思想主要分两个部分,一是把链拆成若干个连续的区间用线段树维护区间信息,二是将所有的区间合并成链,我们既然已经解决了第一个部分,第二个部分的做法就比较显然了。
对于一条链上的查询,如下图:
黑色箭头所指的方向是我们的 \(\text{dfs}\) 序的方向,也就是我们线段树的方向,也就是说,对于线段树而言,图中黑色的 \(l,r\) 是它认为的左边和右边。
但我们实际想要查询的方向是蓝色箭头所指的方向,我们发现,在从 \(u\to \text{LCA}(u,v)\) 的路径上,线段树的方向与我们想要查询的方向南辕北辙,为了解决这个问题,我们在链上的合并时,先从起点和终点分别按照线段树方向维护两个链上的信息,在最后一步时将起点所在链的信息翻转,再与终点链的信息合并,从而得到完整的信息。
这么说可能有点抽象,具体看代码。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100100;//双向边,不要在乎空间,全部开双倍
int to[N],nxt[N],head[N],w[N];//链星
int top[N],fa[N],dfn[N],rnk[N],siz[N],dep[N],son[N];//树剖七件套
int idx,cnt,n,q,in1,in2,in3;
void add(int u,int v){idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;}
void Swap(int &x,int &y){int t=x;x=y;y=t;}
struct STn{int l,r,max,min,atob,btoa,t;};//线段树节点,t是懒标记
void merge(STn &res,STn ls,STn rs){//合并信息
res.max=max(ls.max,rs.max);
res.min=min(ls.min,rs.min);
res.atob=max(max(ls.atob,rs.atob),ls.max-rs.min);
res.btoa=max(max(ls.btoa,rs.btoa),rs.max-ls.min);
}
struct ST{//常规线段树
STn a[N<<2];
void add_t(int p,int k){a[p].t+=k;a[p].max+=k;a[p].min+=k;return ;}//区间加
void push_down(int p){if(a[p].t){add_t(p<<1,a[p].t);add_t(p<<1|1,a[p].t);a[p].t=0;}return ;}//下放懒标记
void build(int p,int l,int r){//常规建树
a[p].l=l;a[p].r=r;a[p].t=0;
if(a[p].l==a[p].r){a[p].min=a[p].max=w[rnk[a[p].l]];a[p].atob=a[p].btoa=0;return ;}//初值
int mid=(a[p].l+a[p].r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
merge(a[p],a[p<<1],a[p<<1|1]);return ;
}
void add(int p,int l,int r,int k){//常规的区间加
if(l<=a[p].l&&a[p].r<=r){add_t(p,k);return ;}
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(l<=mid) add(p<<1,l,r,k);if(r>mid) add(p<<1|1,l,r,k);
merge(a[p],a[p<<1],a[p<<1|1]);return ;
}
STn ask(int p,int l,int r){//常规的区间查询
if(l<=a[p].l&&a[p].r<=r) return a[p];
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(r<=mid) return ask(p<<1,l,r);
if(l>mid) return ask(p<<1|1,l,r);
STn res;merge(res,ask(p<<1,l,r),ask(p<<1|1,l,r));
return res;
}
}tree;
void dfs_1(int s,int gr){//常规的树剖dfs1
dep[s]=dep[gr]+1;fa[s]=gr;
son[s]=-1;siz[s]=1;
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v==gr) continue;
dfs_1(v,s);
siz[s]+=siz[v];
if(son[s]==-1||siz[v]>siz[son[s]]) son[s]=v;
}
}
void dfs_2(int s,int tp){//常规的树剖dfs2
top[s]=tp;dfn[s]=++cnt;rnk[cnt]=s;
if(son[s]==-1) return ;
dfs_2(son[s],tp);
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v!=son[s]&&v!=fa[s]) dfs_2(v,v);
}
}
void add_all(int x,int y,int k){//常规的链上加
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) Swap(x,y);
tree.add(1,dfn[top[x]],dfn[x],k);x=fa[top[x]];
}
tree.add(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),k);
}
int query(int x,int y){//不常规的查询
STn l={0,0,-0x3f3f3f3f,0x3f3f3f3f,0,0,0},r=l;//先把两条链的初值赋上
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){merge(r,tree.ask(1,dfn[top[y]],dfn[y]),r);y=fa[top[y]];}//分起点和终点,不能swap
else{merge(l,tree.ask(1,dfn[top[x]],dfn[x]),l);x=fa[top[x]];}
//注意点:合并时 l,r 应该放在后边作为右区间进行合并
}
if(dep[x]>dep[y]) merge(l,tree.ask(1,dfn[y],dfn[x]),l);
else merge(r,tree.ask(1,dfn[x],dfn[y]),r);//分两种完成最后一次合并
return max(max(l.atob,r.btoa),r.max-l.min);//这里没有把区间翻转,而是直接利用区间信息完成合并
//注意点:如何合并,结合图像理解
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<n;i++){
scanf("%d%d",&in1,&in2);
add(in1,in2);add(in2,in1);
}//常规输入
dfs_1(1,0);dfs_2(1,1);
tree.build(1,1,n);//常规预处理
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&in1,&in2,&in3);
cout<<max(query(in1,in2),0)<<'\n';//肯定不会亏本吧
add_all(in1,in2,in3);//完事之后区间加
}
return 0;
}
标签:rs,int,题解,min,btoa,旅游,max,ls
From: https://www.cnblogs.com/TKXZ133/p/17458268.html