首页 > 其他分享 >树链剖分入门

树链剖分入门

时间：2023-02-02 10:55:53浏览次数：59  
标签：入门 剖分 int top 树链 dep dfn swap void

目录

树链剖分

这玩意也是才开始预习，写得不好勿喷。

约定记号：

  1. \(siz[x]\)，\(x\)为根的子树节点数
  2. \(son[x]\)，\(x\)的重儿子
  3. \(top[x]\)，\(x\)所在重链的链顶
  4. \(f[x]\)，\(x\)的父亲节点
  5. \(dfn[x]\)，\(x\)的DFS序
  6. \(dep[x]\)，\(x\)的深度
  7. \(rew[x]\)，DFS序为\(x\)的节点(与\(dfn\)构成一对映射)
  8. \(id[x]\)，边权下放点权的时候节点\(x\)所代表的边
  9. \(t[x]\)，\(x\)所代表的线段树区间
  10. \((u,v)\)，由\(u\)到\(v\)的路径或者边\((u,v)\)
  11. 默认\(u\)是父亲，\(v\)是儿子

算法思想

顾名思义，树链剖分算法是将一颗树剖分成若干不重合的链进行处理，这也是我们一般处理复杂树上路径问题的利器。

我们一般所说的树链剖分还有一个名字：轻重链剖分。

它基于以下特殊剖法：

设\(siz[x]\)表示以\(x\)为根的子树大小。

则每个节点\(x\)选取其\(siz\)值最大的子节点\(y\)加入\(x\)所在的链，其余子节点新开链。

我们称\(y\)这个儿子为\(x\)的重儿子，其余为轻儿子，每个点连接它的重儿子的边称为重边，由重边所组成的链为重链，连接两条重链的边为轻边。链头为一条重链上深度最小的节点。注意：链即使只有一个节点也是一条链。

性质：

  1. 链头都是轻儿子，证明显然。
  2. 若\((u,v)\)是轻边，则\(siz[v]<\frac{siz[u]}{2}\)
  3. 根节点\(rt\)到\(u\)的路径上，不会超过\(O(\log n)\)条重链

证明：当树为一条链的时候显然成立。当树为多叉树时，原命题等价于只有不超过\(O(\log n)\)条轻边，结合性质2，可知每次走轻边，最优也会使子树大小减半，所以最多走\(O(\log n)\)条轻边的时候，子树大小变成了1,故成立。

下面我们尝试写出算法实现。

实现是由两个dfs完成。第一个dfs负责统计\(siz\)和重儿子\(son\)以及\(fa,dep\)等数据。第二个dfs负责进行链的统计，维护如\(top[x]\)表示\(x\)所在重链的顶点的dfs序，对节点进行编号。

为了方便维护，我们使重链上的点编号连续，所以每个节点优先递归重儿子。

void dfs1(int u,int fa){
	siz[u]=1,f[u]=fa,dep[u]=dep[fa]+1;
	int mx=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(mx<siz[v]){
			son[u]=v;mx=siz[v];
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++num;
	rew[num]=u;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

这样的做法有两个好处：

  1. 每条重链编号连续，这意味着我们可以将其抽象在序列上使用线段树等进行维护
  2. 每个节点及其整个子树的节点编号不重不漏覆盖了区间\([id[x],id[x]+siz[x]-1]\)，便于对子树进行维护

所以树链剖分可以方便的支持树上路径操作和子树操作。

一个基础操作是食用树链剖分求解节点\(u,v\)的LCA，简单的想法是：

  1. 当\(top[u]\neq top[v]\)，此时选择深度较大者(注意是链顶的深度)向上跳到链顶的父亲节点(进入另一条重链)
  2. 在一条重链上的时候，直接选择深度较小者即可。

这个过程对我们有没有什么启发呢？有！

在每一次跳链的时候，可以执行对这条链的修改操作！最后在一条链上的时候也同样可以。

所以这样我们就完成了修改。

对于修改操作，有两类实现方式，第一类是边跳边修改，第二类是先求出LCA，然后只处理向上的链的修改，在此笔者推荐采用第二种方式。

树链剖分的简单题，其实现难度和思维难度主要在于维护链的数据结构，树剖其实是一个很板的东西。

例题：

模版-树链剖分

板子题不解释，可以看代码注释。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long
struct node{
	int l,r;ll sum,lz;
};
#define N 200500
int dfn[N],top[N],son[N],rew[N],n,m,a[N],now,siz[N],head[N],ver[N],nxt[N],rt,tot,f[N],dep[N],num,p;//rew:映射 
struct Node{//线段树 
	node t[N<<2];int n;
	#define lc x<<1
	#define rc x<<1|1
	void pushup(int x){
		t[x].sum=t[lc].sum+t[rc].sum;
		t[x].sum%=p;
	}
	void pushdown(node &a,node &b,node &c){
		b.lz+=a.lz,c.lz+=a.lz;
		b.lz%=p;c.lz%=p;
		b.sum+=a.lz*(b.r-b.l+1);
		c.sum+=a.lz*(c.r-c.l+1);
		c.sum%=p;b.sum%=p;
		a.lz=0;	
	}
	void pushdown(int x){
		if(t[x].lz==0)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void build(int x,int l,int r){
		int mid=l+r>>1;
		t[x].l=l,t[x].r=r,t[x].lz=0;
		if(l==r){
			t[x].sum=a[rew[l]];//rew:映射 
			return ;
		}
		build(lc,l,mid);build(rc,mid+1,r);
		pushup(x);
	}	
	void change(int x,int l,int r,int k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].sum+=k*(t[x].r-t[x].l+1);
			t[x].lz+=k;
			t[x].sum%=p;t[x].lz%=p;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[lc].r<r)change(rc,l,r,k);
		pushup(x);
	}
	ll find(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r){
			return t[x].sum;
		}
		pushdown(x);ll ans=0;
		if(l<=t[lc].r)ans=(find(lc,l,r)+ans)%p;
		if(t[lc].r<r)ans=(ans+find(rc,l,r))%p;
		pushup(x);return (ans%p+p)%p;
	}
}s; //线段树的基本操作，推荐封装为结构体，方便一些 
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs1(int u,int fa){
	siz[u]=1,f[u]=fa,dep[u]=dep[fa]+1;
	int mx=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(mx<siz[v]){
			son[u]=v;mx=siz[v];
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++num;
	rew[num]=u;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}//两个dfs不多说 
void init(){
	cin>>n>>m>>rt>>p;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs1(rt,0);
	dfs2(rt,rt);
	s.build(1,1,n);//别忘了初始化 
}
ll query1(int u,int v){
	ll ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);//注意比较的是链顶的深度,这里采用第一种实现方式 
		ans+=s.find(1,dfn[top[v]],dfn[v]);ans%=p;
		v=f[top[v]];
	}	
	if(dep[u]>dep[v])swap(u,v);
	ans+=s.find(1,dfn[u],dfn[v]);
	return (ans%p+p)%p;
}
ll query2(int u){
	return s.find(1,dfn[u],dfn[u]+siz[u]-1);
}
void change1(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u],dfn[v],k);
}
void change2(int u,int k){
	s.change(1,dfn[u],dfn[u]+siz[u]-1,k);
}//常规操作 
void solve(){
	while(m--){
		int opt,x,y,z;
		cin>>opt;
		if(opt==1){
			cin>>x>>y>>z;
			change1(x,y,z);
		}
		else if(opt==2){
			cin>>x>>y;
			cout<<query1(x,y)<<"\n";
		} 
		else if(opt==3){
			cin>>x>>y;
			change2(x,y);
		}
		else {
			cin>>x;
			cout<<query2(x)<<"\n";
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

旅行

题意：给定一颗树，每个节点都有自己的颜色和权值，需要支持4个操作

  1. 修改一个节点的颜色
  2. 修改一个节点的权值
  3. 查询两个颜色相同的节点路径上与其颜色相同的节点的权值和
  4. 查询两个颜色相同的节点路径上与其颜色相同的节点的权值最大值

分析：

这玩意一看就非常难搞，实际非常简单。

这个玩意节点是不多的，所以可以对每个颜色开一棵线段树进行维护，当然由于空间问题就只能动态开点了。

对于修改颜色，就等同于在原颜色的线段树中把权值置为0，在新颜色中更改权值
对于修改权值，直接在线段树里改就好了
对于查询路径，树剖板子

#include<iostream>
#include<cstdio>
using namespace std; 
#define N 1000400
int a[N],val[N],tot,num,head[N],ver[N<<1],nxt[N<<1],dfn[N],top[N],f[N],son[N],siz[N],cnt,dep[N],n,m;
struct node{
	int sum,lc,rc,mx;
}t[N<<3];
struct Node{
	int rt;
	void pushup(int x){
		t[x].sum=t[t[x].lc].sum+t[t[x].rc].sum;
		t[x].mx=max(t[t[x].lc].mx,t[t[x].rc].mx);
		return ;
	}
	void updata(int &x,int pos,int L,int R,int k){
		if(!x)x=++cnt;
		if(L==R){
			t[x].sum=t[x].mx=k;
			return ;
		}
		int mid=L+R>>1;
		if(pos<=mid)updata(t[x].lc,pos,L,mid,k);
		else updata(t[x].rc,pos,mid+1,R,k);
		pushup(x);
		return ;
	}
	int find1(int &x,int l,int r,int L,int R){
		if(!x)x=++cnt;
		if(l<=L&&R<=r)return t[x].sum;
		int ans=0;
		int mid=L+R>>1;
		if(l<=mid)ans+=find1(t[x].lc,l,r,L,mid);
		if(mid<r)ans+=find1(t[x].rc,l,r,mid+1,R);
		return ans;
	}
	int find2(int &x,int l,int r,int L,int R){
		if(!x)x=++cnt;
		if(l<=L&&R<=r)return t[x].mx;
		int ans=0;
		int mid=L+R>>1;
		if(l<=mid)ans=max(ans,find2(t[x].lc,l,r,L,mid));
		if(mid<r)ans=max(ans,find2(t[x].rc,l,r,mid+1,R));
		return ans;
	}
}s[N];
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
	return ;
}
void dfs1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1;
	siz[u]=1;int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>len)son[u]=v,len=siz[v];
	} 
	return ;
} 
void dfs2(int u,int tp){
	top[u]=tp;dfn[u]=++num;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
	return ;
}
void change1(int u,int k){
	s[a[u]].updata(s[a[u]].rt,dfn[u],1,n,0);
	a[u]=k;
	s[a[u]].updata(s[a[u]].rt,dfn[u],1,n,val[u]);
	return ;
} 
void change2(int u,int k){
	val[u]=k;
	s[a[u]].updata(s[a[u]].rt,dfn[u],1,n,val[u]);
	return ;
}
int query1(int u,int v){
	int ans=0,k=a[u];
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		ans+=s[k].find1(s[k].rt,dfn[top[v]],dfn[v],1,n);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ans+=s[k].find1(s[k].rt,dfn[u],dfn[v],1,n);
	return ans;
}
int query2(int u,int v){
	int ans=0,k=a[u];
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		ans=max(ans,s[k].find2(s[k].rt,dfn[top[v]],dfn[v],1,n));
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ans=max(ans,s[k].find2(s[k].rt,dfn[u],dfn[v],1,n));
	return ans;
}
void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>val[i]>>a[i];
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++)s[a[i]].updata(s[a[i]].rt,dfn[i],1,n,val[i]);
	return ;
}
void solve(){
	while(m--){
		char x[3];int u,v,k;
		cin>>x;
		if(x[0]=='C'&&x[1]=='C'){
			cin>>u>>k;change1(u,k);
		}
		if(x[0]=='C'&&x[1]=='W'){
			cin>>u>>k;change2(u,k);
		}
		if(x[0]=='Q'&&x[1]=='S'){
			cin>>u>>v;
			cout<<query1(u,v)<<"\n";
		}
		if(x[0]=='Q'&&x[1]=='M'){
			cin>>u>>v;
			cout<<query2(u,v)<<"\n";
		}
	}
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

P4374

容易发现，加入一条边之后会构成一个环，此时环上的所有边(除了新加边)，在断开它后这条边都是一个替代的选择。

所以可以使用树剖，边下放到点，然后维护一个区间取\(\min\)即可。事实上，将替代边的边权从大到小排序，依次加入，直接打上懒标记当区间赋值就行。

然后依次单点查询就OK。注意边下放到了点之后LCA不能算哦，所以就可以直接s.change(1,dfn[u]+1,dfn[v],k);。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 500505
struct edge{
	int u,v,w;
	bool operator<(const edge b){
		return w>b.w;
	}
}b[N];
int n,m,dfn[N],head[N],ver[N],nxt[N],tot,num,top[N],f[N],rew[N],dep[N],son[N],siz[N];
struct node{
	int l,r,val,lz;
}t[N<<2];
struct Node{
	#define lc x<<1
	#define rc x<<1|1
	void pushdown(node &a,node &b,node &c){
		b.lz=c.lz=a.lz;
		b.val=c.val=a.lz;a.lz=0;
	}
	void pushdown(int x){
		if(t[x].lz==0)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void build(int x,int l,int r){
		t[x]={l,r,0,0};
		if(l==r)return ;
		int mid=l+r>>1;
		build(lc,l,mid);build(rc,mid+1,r);
	}
	void change(int x,int l,int r,int k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].val=t[x].lz=k;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[lc].r<r)change(rc,l,r,k);
	}
	int find(int x,int pos){
		if(t[x].l==t[x].r)return t[x].val;
		pushdown(x);
		if(pos<=t[lc].r)return find(lc,pos);
		return find(rc,pos);
	}
}s;
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		rew[(i+1)/2]=v;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>len)son[u]=v,len=siz[v];
	}
}
void dfs2(int u,int tp){
	top[u]=tp;dfn[u]=++num;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
void init(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=m;i++)cin>>b[i].u>>b[i].v>>b[i].w;
	sort(b+1,b+m+1);dfs1(1,0);dfs2(1,1);
}
void query(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	if(dfn[u]==dfn[v])return ;
	s.change(1,dfn[u]+1,dfn[v],k);
}
void solve(){
	s.build(1,1,n);
	for(int i=1;i<=m;i++){
		query(b[i].u,b[i].v,b[i].w);
	}
	for(int i=1;i<n;i++){
		int ans=s.find(1,dfn[rew[i]]);
		if(ans==0)ans=-1;
		cout<<ans<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

然后就是，这个做法具有优化的空间。可以使用并查集+向上标记法，将替代边按边权从小到大排序，然后暴力跳并食用并查集标记跳完后的上面一个节点，修改的时候暴力跳暴力改就完了。。。

一遍过就是爽

P4211

这种题肯定是一眼差分题。

那么问题变为：给定\(z\)，求\(\sum_{i=1}^rdep[LCA(z,i)]\)。

显然可以离线，借助充分利用历史答案的思想，将右端点递增排序。

然后考虑怎么维护。这里需要用到\(dep\)的本质：根到这个点的总共遇到的节点个数。

考虑单求\(dep[LCA(x,y)]\)怎么办。一种方法是求出LCA，另一种方法是暴力跳链法。

暴力的向上跳链不仅仅可以自底向上，也可以自上而下，也即将\((rt,u)\)每个点都加上1，那么\(dep[LCA(u,v)]\)就是\(\sum (rt,v)\)

这启发我们：插入一个点\(x\)，就等价于将根到\(x\)路径上的所有点点权+1，故食用一个指针维护操作

一次询问\(z\)的结果就是根到\(z\)的点权和(此时指针等于\(r\))

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 500050
#define ll long long
const ll p=201314;
struct node{
	int l,r;
	ll sum,lz;
}t[N<<2]; 
struct Node{
	#define lc x<<1
	#define rc x<<1|1
	inline void pushup(int x){
		t[x].sum=t[lc].sum+t[rc].sum;
		t[x].sum%=p; 
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].sum=t[x].lz=0;
		if(l==r)return ;
		int mid=l+r>>1;
		build(lc,l,mid);build(rc,mid+1,r);
	}
	void pushdown(node &a,node &b,node &c){
		b.lz+=a.lz,c.lz+=a.lz;
		b.sum+=(b.r-b.l+1)*a.lz;
		c.sum+=(c.r-c.l+1)*a.lz;
		b.lz%=p,c.lz%=p,b.sum%=p,c.sum%=p;
		a.lz=0;
	}
	void pushdown(int x){
		if(t[x].lz==0)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void change(int x,int l,int r,ll k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].lz+=k,t[x].sum+=k*(t[x].r-t[x].l+1);
			t[x].lz%=p,t[x].sum%=p;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[lc].r<r)change(rc,l,r,k);
		pushup(x);
	}
	ll find(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r)return t[x].sum;
		ll ans=0;
		pushdown(x);
		if(l<=t[lc].r)ans+=find(lc,l,r);
		if(t[lc].r<r)ans+=find(rc,l,r);
		return ans%p;
	}
}s;
struct ask{
	int id,x,u,tag;
	bool operator<(const ask b){
		return x<b.x;
	}
}ask[N];
int ans[N],dfn[N],num,top[N],son[N],siz[N],n,m,tot,head[N],ver[N],nxt[N],f[N],rt,cnt,dep[N];
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs1(int u,int fa){
	siz[u]=1,dep[u]=dep[f[u]]+1;int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(len<siz[v])son[u]=v,len=siz[v];
	}
}
void dfs2(int u,int tp){
	top[u]=tp;dfn[u]=++num;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==son[u]||v==f[u])continue;
		dfs2(v,v);
	} 
}
void init(){
	cin>>n>>m;dep[1]=1;
	for(int i=2;i<=n;i++){
		int u;cin>>u;++u;
		f[i]=u;add(u,i);add(i,u);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=m;i++){
		int l,r,u;cin>>l>>r>>u;
		l++,r++,u++;
		ask[++cnt].id=i,ask[cnt].tag=-1,ask[cnt].x=l-1,ask[cnt].u=u;
		ask[++cnt].id=i,ask[cnt].tag= 1,ask[cnt].x=r  ,ask[cnt].u=u;
	}
	sort(ask+1,ask+cnt+1);
	s.build(1,1,n);
}
void updata(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u],dfn[v],k);
}
ll query(int u,int v){
	ll ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		ans+=s.find(1,dfn[top[v]],dfn[v]);
		ans%=p;
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	ans+=s.find(1,dfn[u],dfn[v]);
	return ans%p; 
}
void solve(){
	int q=0;
	for(int i=1;i<=cnt;i++){
		while(q<ask[i].x)updata(1,++q,1);
		ans[ask[i].id]+=ask[i].tag*query(1,ask[i].u);
	}
	for(int i=1;i<=m;i++)cout<<(ans[i]%p+p)%p<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

CF1023F

其实是P4374的一个变式。

原题意思就是：给定一个无向连通图，边分黑白，黑边定权，白边不定。求一个白边边权分配方案，使得边权和最大且原图的最小生成树包含所有白边。

求出白边边权和的最大值即可。

可以确定的信息是这颗生成树的形态：先把所有的白边加入生成树，然后将黑边边权从小到大排序后依次加入生成树，接着我们就考虑剩下的边：

剩下的每条边\((u,v)\)事实上都是一个限制：生成树上\(u,v\)路径上的所有边边权不能大于它。显然黑边肯定是不能大于的，这个就是在限制白边。

故可以对所有的剩下的边在生成树上的路径上的白边取\(\min\)，最初设为无限大。同样，为了避免复杂的生成树操作，我仍然选用将剩下的边边权从大到小排。

然后直接区间赋值即可。

选择将边权下放到点权，然后对边的编号和点建立一个双射，就可以查询了。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 505050
struct edge{
	int u,v,w;
}a[N],b[N];
struct node{
	int l,r,mn,lz;
}t[N<<2];
#define ll long long
struct Node{
	#define lc x<<1
	#define rc x<<1|1 
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].mn=2e9,t[x].lz=-1;
		if(l==r)return ;
		int mid=l+r>>1;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	void pushdown(int x){
		if(t[x].lz==-1)return ;
		t[lc].lz=t[rc].lz=t[lc].mn=t[rc].mn=t[x].lz;
		t[x].lz=-1;
	}
	void change(int x,int l,int r,int k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].lz=t[x].mn=k;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[lc].r<r)change(rc,l,r,k);
	}
	int find(int x,int pos){
		if(t[x].l==t[x].r)return t[x].mn;
		pushdown(x);
		if(pos<=t[lc].r)return find(lc,pos);
		return find(rc,pos);
	}
}s;
int dfn[N],tot,f[N],num,head[N],ver[N<<1],nxt[N<<1],vis[N<<1],rew[N<<1],siz[N],son[N],top[N],dep[N],n,m,k,fa[N],id[N<<1],cnt;
void dfs1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		id[v]=(i+1)/2,rew[id[v]]=v; 
		dfs1(v,u);siz[u]+=siz[v];
		if(len<siz[v])len=siz[v],son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;dfn[u]=++num;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==son[u]||v==f[u])continue;
		dfs2(v,v);
	} 
}
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
bool cmp1(edge a,edge b){
	return a.w<b.w;
}
bool cmp2(edge a,edge b){
	return a.w>b.w;
}
int get(int x){
	return x==fa[x]?x:fa[x]=get(fa[x]);
}
void merge(int u,int v){
	u=get(u),v=get(v);
	if(u==v)return ;
	fa[u]=v;
}
void init(){
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=k;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);merge(u,v);
	}
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		a[i]=(edge){u,v,w};
	}
	sort(a+1,a+m+1,cmp1);
	for(int i=1;i<=m;i++){
		int u=get(a[i].u),v=get(a[i].v);
		if(v==u)continue;
		add(a[i].u,a[i].v);
		add(a[i].v,a[i].u);
		fa[u]=v;vis[i]=1;
	}
	for(int i=1;i<=m;i++){
		if(!vis[i])b[++cnt]=a[i];
	}
	sort(b+1,b+cnt+1,cmp2);
	dfs1(1,0);
	dfs2(1,1);
	s.build(1,1,n);
}
void query(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u]+1,dfn[v],k);
}
void solve(){
	for(int i=1;i<=cnt;i++)query(b[i].u,b[i].v,b[i].w);
	ll ans=0;
	for(int i=1;i<=k;i++){
		int d=s.find(1,dfn[rew[i]]);
		if(d>=2e9){
			cout<<"-1\n";return ;
		}
		ans+=d;
	}
	cout<<ans<<"\n";
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

P1505

树剖的板子题。对于其他的维护就不多说了，主要是变成相反数这个。

维护懒标记lz，每次更新就把lz^=1就行，然后最大值最小值swap一下然后取个负就行。区间和也就是取个负。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 200050
int head[N],ver[N<<1],nxt[N<<1],rew[N],dfn[N],siz[N],son[N],dep[N],f[N],top[N],num,tot,n,m,cnt,id[N],pos[N];
struct edge{
	int u,v,w;
}a[N];
struct node{
	int l,r,mx,mn,sum,lz;
}t[N<<2];
void pushup(node &a,node &b,node &c){
	a.sum=b.sum+c.sum,a.mn=min(c.mn,b.mn);
	a.mx=max(c.mx,b.mx);
}
struct Node{
	#define lc x<<1
	#define rc x<<1|1
	void pushup(node &a,node &b,node &c){
		a.sum=b.sum+c.sum,a.mn=min(c.mn,b.mn);
		a.mx=max(c.mx,b.mx);
	}
	void pushup(int x){
		pushup(t[x],t[lc],t[rc]);
	}
	void pushdown(node &a,node &b,node &c){
		swap(b.mn,b.mx),swap(c.mx,c.mn);
		b.mn*=-1,b.mx*=-1,c.mx*=-1,c.mn*=-1;
		b.sum*=-1,c.sum*=-1;
		b.lz^=1,c.lz^=1;
		a.lz=0;
	}
	void pushdown(int x){
		if(!t[x].lz)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].lz=0;
		if(l==r){
			t[x].mx=t[x].mn=t[x].sum=a[id[rew[l]]].w;
			return ;
		}
		int mid=l+r>>1;
		build(lc,l,mid);build(rc,mid+1,r);
		pushup(x);
	}
	void change(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r){
			swap(t[x].mn,t[x].mx);t[x].sum*=-1,t[x].mn*=-1,t[x].mx*=-1;
			t[x].lz^=1;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r);
		if(t[rc].l<=r)change(rc,l,r);
		pushup(x);
	}
	void updata(int x,int pos,int k){
		if(t[x].l==t[x].r){
			t[x].sum=t[x].mn=t[x].mx=k;
			return ;
		}
		pushdown(x);
		if(pos<=t[lc].r)updata(lc,pos,k);
		else updata(rc,pos,k);
		pushup(x);
	}
	node find(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r)return t[x];
		pushdown(x);
		node ans1;ans1.mn=1e9,ans1.mx=-1e9,ans1.sum=0;
		node ans2=ans1;
		if(l<=t[lc].r)ans1=find(lc,l,r);
		if(t[rc].l<=r)ans2=find(rc,l,r);
		pushup(ans1,ans1,ans2);
		return ans1;
	}
}s; 
void query(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v]);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u]+1,dfn[v]);
}
node find(int u,int v){
	node ans;ans.mn=1e9,ans.mx=-1e9,ans.sum=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		node sum=s.find(1,dfn[top[v]],dfn[v]);
		pushup(ans,ans,sum);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	node sum=s.find(1,dfn[u]+1,dfn[v]);
	pushup(ans,ans,sum);
	return ans;
}
void dfs1(int u,int fa){
	siz[u]=1,f[u]=fa,dep[u]=dep[f[u]]+1;int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		id[v]=(i+1)/2,pos[id[v]]=v;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(len<siz[v])son[u]=v,len=siz[v];
	}
}
void dfs2(int u,int tp){
	top[u]=tp;dfn[u]=++num,rew[num]=u;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==son[u]||v==f[u])continue;
		dfs2(v,v);
	} 
}
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void init(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;cin>>u>>v>>w;
		u++,v++;
		add(u,v);add(v,u);a[i]=(edge){u,v,w};
	}
	dfs1(1,0);
	dfs2(1,1);
	s.build(1,1,n);
}
void solve(){
	cin>>m;
	char opt[5];int u,v,w;
	while(m--){
		cin>>opt;
		if(opt[0]=='C'){
			cin>>v>>w;a[v].w=w;
			s.updata(1,dfn[pos[v]],w);
		}
		else if(opt[0]=='N'){
			cin>>u>>v;u++,v++;query(u,v);
		}
		else {
			cin>>u>>v;u++,v++;
			node ans=find(u,v);
			if(opt[1]=='U')cout<<ans.sum<<"\n";
			if(opt[1]=='A')cout<<ans.mx<<"\n";
			if(opt[1]=='I')cout<<ans.mn<<"\n";
		}
	}
	return ;
}
int main(){
//  fc D:\编程\C++\P1505_1.ans D:\编程\C++\P1505_1.out
//	freopen("P1505_1.in","r",stdin);
//	freopen("P1505_1.ans","w",stdout);
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

P2486

线段树维护颜色块数量就不多说了，树剖向上合并的时候和线段树合并规则是一样的。

代码在合并的时候细节有点多，标注在里面了。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 500050
struct node{
	int l,r,lx,rx,cnt,lz;
}t[N<<1]; 
node merge(node b,node c){
	if(b.lx==0&&b.rx==0)return c;
	if(c.lx==0&&c.rx==0)return b;
	node ans;
	ans.lx=(b.lx?b.lx:c.lx),ans.rx=(c.rx?c.rx:b.rx);
	ans.cnt=b.cnt+c.cnt-(b.rx==c.lx);
	return ans;
}
int dfn[N],head[N],ver[N<<1],nxt[N<<1],tot,num,n,m;
int son[N],f[N],top[N],dep[N],rew[N],val[N],siz[N];
struct Node{
	#define lc x<<1
	#define rc x<<1|1 
	void pushup(node &a,node &b,node &c){
		a.cnt=b.cnt+c.cnt-(b.rx==c.lx);
		a.lx=b.lx,a.rx=c.rx;
	}
	void pushup(int x){
		pushup(t[x],t[lc],t[rc]);
	}
	void pushdown(node &a,node &b,node &c){
		b.lz=a.lz,c.lz=a.lz;
		b.lx=b.rx=c.lx=c.rx=a.lz;
		b.cnt=1,c.cnt=1;
		a.lz=0;
	}
	void pushdown(int x){
		if(!t[x].lz)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].lz=0;
		if(l==r){
			t[x].lx=t[x].rx=val[rew[l]];
			t[x].cnt=1;
			return ; 
		}
		int mid=l+r>>1;
		build(lc,l,mid);build(rc,mid+1,r);
		pushup(x);
	}
	void change(int x,int l,int r,int k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].cnt=1,t[x].lx=t[x].rx=k;
			t[x].lz=k;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[rc].l<=r)change(rc,l,r,k);
		pushup(x); 
	} 
	node find(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r)return t[x];
		node s1,s2;s1.lx=s1.rx=0;s1.cnt=1;
		s2=s1;
		pushdown(x);
		if(l<=t[lc].r)s1=find(lc,l,r);
		if(t[rc].l<=r)s2=find(rc,l,r);
		pushup(x);return merge(s1,s2);
	}
}s;
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void dfs1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>len)son[u]=v,len=siz[v]; 
	}
}
void dfs2(int u,int tp){
	top[u]=tp,dfn[u]=++num,rew[num]=u;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==f[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=2;i<=n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u); 
	}
	dfs1(1,0);dfs2(1,1);
	s.build(1,1,n);
}
int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	return u;
}
void change(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u],dfn[v],k); 
}
int query(int u,int v){
	int k=LCA(u,v);
	node s1,s2;s1.lx=s1.rx=0;s1.cnt=1;
	s2=s1;
	while(top[u]!=top[k]){
		s1=merge(s.find(1,dfn[top[u]],dfn[u]),s1);//由于线段树的关系，只能以下面的链为右儿子
		u=f[top[u]];	
	}
	s1=merge(s.find(1,dfn[k],dfn[u]),s1);
	swap(s1.lx,s1.rx);//但事实上需要u->LCA(u,v)的链是以LCA(u,v)为右端点的(判断合并)，故翻转一下区间
	while(top[v]!=top[k]){
		s2=merge(s.find(1,dfn[top[v]],dfn[v]),s2);
		v=f[top[v]];
	}
	s2=merge(s.find(1,dfn[k],dfn[v]),s2);
	return merge(s1,s2).cnt; 
}
void solve(){
	while(m--){
		char x;int u,v,k;
		cin>>x;
		if(x=='Q'){
			cin>>u>>v;
			cout<<query(u,v)<<"\n";
		}
		else {
			cin>>u>>v>>k;
			change(u,v,k);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

P7735

NOI真题，典中典。

首先问题在于一类操作，不可能真的修改轻重边，按照树剖的套路，肯定只能修改这条链。那么问题来了，在只能修改链的情况下，如何判断一条边\((u,v)\)是重边。

如果对染色很有灵感的同学，应该可以想到：每一次都给路径上的点染上一种与众不同的颜色，那么\((u,v)\)是重边的充要条件是两点颜色相同。

这就好办了，最初给所有点分别染上颜色\(1\sim n\)，然后对于每一次修改染上颜色\(i+n\)即可。

至于线段树维护和树剖的维护，都是比区间合并部分的两端点颜色是否相同即可。

P3976

形式化题意：每次询问支持两个操作

  1. 给定路径\((u,v)\)，支持给路径上所有点权值加上\(k\)。
  2. 给定路径\((u,v)\)，求\(\max_{a\in (u,b),b\in(u,v)}\lbrace val_a-val_b\rbrace\)

考虑简化版问题：给定序列\(a_1\sim a_n\)，若干次询问，给定\(l,r\)，求\(\max_{l\le p\le q,p\le q\le r}\lbrace a_p-a_r\rbrace\)

这有点像最小子段和的求法——如果我们把\(a\)视作一个前缀和的话。

那么类比最小子段和，不难想到开一棵线段树维护：

  1. \(t[x].mx\)维护区间最大值
  2. \(t[x].mn\)维护区间最小值
  3. \(t[x].ans\)维护答案

考虑维护更新

  1. \(t[x].mx=\max\lbrace t[lc].mx,t[rc].mx\rbrace\)
  2. \(t[x].mn=\min\lbrace t[lc].mn,t[rc].mn\rbrace\)
  3. \(t[x].ans=\max\lbrace t[lc].ans,t[rc].ans,t[rc].mx-t[lc].mn\rbrace\)

这就在\(O((n+m)\log n)\)的时间内解决了这个问题。

我们尝试将其扩展到树上，如果仅仅需要考虑\((u,LCA(u,v))\)这条链的话，这个维护方式已经足够。但我们仍然需要考虑\((LCA(u,v),v)\)这条向下的链，这条链是反着的。

为了维护这条链，在区间上讲就是答案就是从右到左的差值最大值变成了从左到右的差值最大值而已，不妨更改一下维护树剖的线段树定义：

  1. \(t[x].lx\)表示从左到右的答案
  2. \(t[x].rx\)表示从右到左的答案

容易得到：

  1. \(t[x].lx=\max\lbrace t[lc].lx,t[rc].lx,t[lc].mx-t[rc].mn\rbrace\)
  2. \(t[x].rx=\max\lbrace t[rc].rx,t[lc].rx,t[rc].mx-t[lc].mn\rbrace\)

对于树剖各个重链答案合并的问题：将下面的链视作右儿子，上跳到的链视为左儿子，当前答案是父亲来搞就行。

最后思考获取答案的问题：

设\(s1,s2\)分别表示\((u,LCA(u,v)),(LCA(u,v),v)\)这两条链最后合并的结果，那么答案显然是：\(\max\lbrace s1.lx,s2.rx,s2.mx-s1.mn\rbrace\)

线段树维护即可。

还有一个区间加的懒标记下传问题：事实上\(t[x].lx,t[x].rx\)不变，\(t[x].mn,t[x].mx\)加上即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 500500
struct node{
	int l,r,lx,rx,mn,mx,lz;
}t[N<<2];
int n,m,dep[N],head[N],ver[N<<1],nxt[N<<1],val[N],siz[N],dfn[N],num,tot,f[N],son[N],top[N],rew[N];
void pushup(node &a,node &b,node &c){
	a.mn=min(b.mn,c.mn);a.mx=max(b.mx,c.mx);
	a.lx=max(b.lx,c.lx),a.rx=max(b.rx,c.rx);
	a.lx=max(a.lx,b.mx-c.mn);
	a.rx=max(a.rx,c.mx-b.mn);
}
struct Node{
	#define lc x<<1
	#define rc x<<1|1 
	void pushup(node &a,node &b,node &c){
		a.mn=min(b.mn,c.mn);a.mx=max(b.mx,c.mx);
		a.lx=max(b.lx,c.lx),a.rx=max(b.rx,c.rx);
		a.lx=max(a.lx,b.mx-c.mn);
		a.rx=max(a.rx,c.mx-b.mn);
	}
	void pushdown(node &a,node &b,node &c){
		b.lz+=a.lz,c.lz+=a.lz;
		b.mn+=a.lz,b.mx+=a.lz;
		c.mn+=a.lz,c.mx+=a.lz;
		a.lz=0;
	}
	void pushup(int x){
		pushup(t[x],t[lc],t[rc]);
	}
	void pushdown(int x){
		if(!t[x].lz)return ;
		pushdown(t[x],t[lc],t[rc]);
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].lz=0;
		if(l==r){
			t[x].mn=t[x].mx=val[rew[l]];
			t[x].lx=t[x].rx=0;
			return ;
		}
		int mid=l+r>>1;
		build(lc,l,mid),build(rc,mid+1,r);
		pushup(x);
	}
	void change(int x,int l,int r,int k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].mn+=k,t[x].mx+=k;
			t[x].lz+=k;
			return ;
		}
		pushdown(x);
		if(l<=t[lc].r)change(lc,l,r,k);
		if(t[rc].l<=r)change(rc,l,r,k);
		pushup(x);
	}
	node find(int x,int l,int r){
		if(l<=t[x].l&&t[x].r<=r)return t[x];
		pushdown(x);
		node s1,s2,ans;s1.lx=s1.rx=0,
		s1.mn=1e9,s1.mx=-1e9,s2=s1;
		if(l<=t[lc].r)s1=find(lc,l,r);
		if(t[rc].l<=r)s2=find(rc,l,r);
		pushup(ans,s1,s2);
		return ans;
	}
}s;
void dfs1(int u,int fa){
	f[u]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	int len=-1;
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>len)son[u]=v,len=siz[v];
	} 
}
void dfs2(int u,int tp){
	top[u]=tp,dfn[u]=++num,rew[num]=u;
	if(!son[u])return ;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=ver[i];
		if(v==son[u]||v==f[u])continue;
		dfs2(v,v);
	}
}
void change(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		s.change(1,dfn[top[v]],dfn[v],k);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	s.change(1,dfn[u],dfn[v],k);
}
int LCA(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]])swap(u,v);
		v=f[top[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	return u;
}
int query(int u,int v){
	int k=LCA(u,v);
	node s1,s2,s3,s4;s1.lx=s1.rx=0,
	s1.mn=1e9,s1.mx=-1e9,s2=s3=s4=s1;
	while(top[u]!=top[k]){
		s3=s.find(1,dfn[top[u]],dfn[u]),s4=s1;
		pushup(s1,s3,s4);
		u=f[top[u]];
	}
	s3=s.find(1,dfn[k],dfn[u]),s4=s1;
	pushup(s1,s3,s4);
	while(top[v]!=top[k]){
		s3=s.find(1,dfn[top[v]],dfn[v]),s4=s2;
		pushup(s2,s3,s4);
		v=f[top[v]];
	}
	s3=s.find(1,dfn[k],dfn[v]),s4=s2;
	pushup(s2,s3,s4);
	return max(max(s1.lx,s2.rx),s2.mx-s1.mn);
}
void add(int u,int v){
	nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
void init(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	cin>>m;
	dfs1(1,0);dfs2(1,1);
	s.build(1,1,n);
}
void solve(){
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		cout<<query(u,v)<<"\n";
		change(u,v,w);
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();solve();
	return 0;
}

Trick总结

  1. 差分配合树剖，dep的本质
  2. 注意可以离线的题目
  3. 树剖上跳维护信息的方式和线段树维护没有本质区别
  4. 对于加边问题，可以考虑加边所作出的限制
  5. 对于删边问题，离线下来倒序处理变删为加
  6. 染色

标签：入门,剖分,int,top,树链,dep,dfn,swap,void
From： https://www.cnblogs.com/oierpyt/p/17085250.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99