P6845 题解 | 动态直径的 dfs 序做法

题意

给一个

n

个点边带权的树，

q

次改边权，每次改完后问树上的直径。强制在线。

保证树上的边权一直是正的。

n,q\leq 10^5

，

w\leq 10^{13}

。

思路

我们可以把直径改写成下面这样的式子：

\max_{i,j}\{d_i+d_j-2d_{lca(i,j)}\}

其中

d_i

表示

i

到根的距离。

把树拍成 dfs 序，设

i

的 dfs 序为

p_i

，那么

d_{lca(i,j)}

就是

x\in[\min(p_i,p_j)+1,\max(p_j)]

中

d_{fa_x}

的最小值。那么如果我们设

a_{p_i}=d_i

，

b_{p_i}=d_{fa_i}

，那么直径就是

\max_{i<j\leq k}\{a_i-2b_j+a_k\}

而修改边权就是对

a

和

b

的区间加。这样我们可以用线段树维护了。具体来说，在线段树上维护以下内容：

$\max_i\{a_i\}$ ， $\min_j\{b_j\}$
$\max_{i<j}\{a_i-2b_j\}$ ， $\max_{j\leq k}\{a_k-2b_j\}$
$\max_{i<j\leq k}\{a_i-2b_j+a_k\}$

即可完成转移。具体转移方式可以看代码。

最后需要注意，对

a

的区间加和对

b

的区间加的区间是不一样的。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct SEG{
	struct st{
		int l,r,z,a,b,ab,bc,abc;
	}a[266666];
	void bt(int x,int l,int r){
		a[x].l=l;
		a[x].r=r;
		if(l<r){
			bt(x<<1,l,(l+r>>1));
			bt(x<<1|1,(l+r>>1)+1,r); 
		}
		else a[x].ab=a[x].abc=-1e18;
	}
	void pu(int x){
		a[x].a=max(a[x<<1].a,a[x<<1|1].a);
		a[x].b=max(a[x<<1].b,a[x<<1|1].b);
		a[x].ab=max({a[x<<1].ab,a[x<<1|1].ab,a[x<<1].a+a[x<<1|1].b});
		a[x].bc=max({a[x<<1].bc,a[x<<1|1].bc,a[x<<1].b+a[x<<1|1].a});
		a[x].abc=max({a[x<<1].abc,a[x<<1|1].abc,a[x<<1].ab+a[x<<1|1].a,a[x<<1].a+a[x<<1|1].bc});
	}
	void ps(int x,int v){
		a[x].a+=v,a[x].b-=v*2;
		a[x].ab-=v,a[x].bc-=v;
		a[x].z+=v;
	}
	void xf(int x){
		ps(x<<1,a[x].z),ps(x<<1|1,a[x].z);
		a[x].z=0;
	}
	void mdf(int x,int l,int r,int v){
		if(a[x].l==l&&a[x].r==r) return ps(x,v);
		xf(x);
		int mid=a[x].l+a[x].r>>1;
		if(r<=mid) mdf(x<<1,l,r,v);
		else if(l>mid) mdf(x<<1|1,l,r,v);
		else mdf(x<<1,l,mid,v),mdf(x<<1|1,mid+1,r,v);
		pu(x); 
	}
	void cg(int x,int p,int v){
		if(a[x].l==a[x].r){
			a[x].b+=v*2;
			a[x].bc+=v*2;
			return;
		}
		xf(x);
		int mid=a[x].l+a[x].r>>1;
		cg(x<<1|(p>mid),p,v);
		pu(x);
	}
	int que(){
		return max(0ll,a[1].abc);
	}
}T;
int n,q,V,w[100005],p[100005],dfn[100005],out[100005],dcnt;
vector<pair<int,int> >e[100005];
void dfs(int x,int f){
	dfn[x]=++dcnt;
	for(auto i:e[x]){
		if(i.first==f) continue;
		dfs(i.first,x);
		p[i.second]=i.first;
	}
	out[x]=dcnt;
}
void ad(int i,int v){
	T.mdf(1,dfn[p[i]],out[p[i]],v);
	T.cg(1,dfn[p[i]],v);
}
signed main(){
	cin>>n>>q>>V;
	for(int i=1,u,v;i<n;i++){
		scanf("%lld %lld %lld",&u,&v,&w[i]);
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
	dfs(1,0);
	T.bt(1,1,n);
	for(int i=1;i<n;i++) ad(i,w[i]);
	for(int i=1,l=0,j,k;i<=q;i++){
		scanf("%lld %lld",&j,&k);
		j=(j+l)%(n-1)+1,k=(k+l)%V;
		ad(j,k-w[j]),w[j]=k;
		printf("%lld\n",l=T.que());
	}
	return 0;
}

P6845 题解 | 动态直径的 dfs 序做法

文章操作

题意

思路

代码

相关推荐

评论

P6845 题解 | 动态直径的 dfs 序做法