P12653 题解

首先用点分治求出

C

。注意之后点分治的过程中都有可能需要特判一端为当前分治中心的路径。

假设从

u

出发走到

v

时进行了归零，那么

(u,v)

对答案的贡献是以

u

为根

v

所在子树大小。而它需要满足条件：路径上权值总和是所有前缀和中的严格最小值。

套路地，在以

r

为分治中心时求出所有经过

r

的路径的贡献。在 dfs 过程中求出每个节点子树大小（注意这个子树是原树的子树，不是当前处理部分的子树）；将一条路径拆成

u\sim r

和

r\sim v

两段，发现

r\sim v

这条路径本身需要满足同样的条件，并且它的边权和要小于某个和

u\sim r

这条链相关的阈值，以防止前面出现更小的前缀和。

那么把阈值当作修改和查询的时间轴进行排序，之后遇到

r\sim v

时累加子树大小，遇到

u\sim r

时查询。

类似地用点分治求

S

。此时不需要像先前那样在归零的地方计算贡献。

在 dfs 过程中求出每个节点子树大小（这里是当前处理部分的子树）；记录

u\sim r

最后一次归零位置和之后的边权和

d_u

。

令

r\sim v

的最小前缀和为

mn_v

，总边权和为

dis_v

。显然只有

dis_v<mn_{fa_v}

时可能出现归零。

同样把阈值当作修改和查询的时间轴进行排序，遇到

u\sim r

时简单查询即可，注意所有没有归零的

r\sim v

都需要加上额外的

d_u

。遇到

r\sim v

时，标记节点

v

的子树。此时它的祖先都没有被标记（它们的

dis

更大，修改时间更晚）。

在标记子树时可以暴力 dfs，如果遇到先前已经被标记的节点就跳出——此时任意一条询问路径都必定在这个位置进行归零，之前是否归零不再重要。否则，更新当前路径的贡献。每个节点至多被标记一次，所以复杂度是对的。也可以预处理每次修改时标记节点的数量和对答案的修改量。

时间复杂度

O(n\log^2 n)

，瓶颈为排序。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (u<<1)
#define rson (u<<1|1)
const ll N=300007;
ll n,root,vis[N],sz[N],SZ[N],s2[N],mn[N],mx[N],p[N],subtr[N],S[N],C[N],dis[N],timer,tI[N],tO[N],id[N],sum[N],cnt[N],tmp[N];
vector<pair<ll,ll> > to[N];
namespace tree{
	ll sz[N],p[N];
	void dfs(int u,int fa){
		sz[u]=1;p[u]=fa;
		for (auto p:to[u]){
			int v=p.first;
			if (v!=fa){
				dfs(v,u);
				sz[u]+=sz[v];
			}
		}
	}
	int query(int u,int fa){
		return fa==p[u]?sz[u]:n-sz[fa];
	}
}
struct node{
	ll tim,op,x;
};
bool cmp(const node& a,const node& b){
	return a.tim==b.tim?a.op>b.op:a.tim>b.tim;
}
vector<node> vec;
void getroot(int u,int fa,int n,int& root){
	sz[u]=1;mx[u]=0;
	for (auto p:to[u]){
		int v=p.first;
		if (v!=fa&&vis[v]==0){
			getroot(v,u,n,root);
			sz[u]+=sz[v];mx[u]=max(mx[u],sz[v]);
		}
	}
	if (max(mx[u],n-sz[u])*2<=n){
		root=u;
	}
}
void dfs(int u,int fa){
	id[tI[u]=++timer]=u;
	sz[u]=SZ[u]=s2[u]=1;p[u]=fa;
	mx[u]=max(mx[fa],dis[u]);
	mn[u]=min(mn[fa],dis[u]);
	vec.emplace_back((node){mx[u],1,u});
	if (dis[u]<mn[fa]){
		vec.emplace_back((node){-dis[u],0,u});
	}
	sum[root]+=dis[u];sum[subtr[u]]+=dis[u];
	for (auto p:to[u]){
		int v=p.first;
		if (v==fa){
			continue;
		}
		if (vis[v]){
			SZ[u]+=tree::query(v,u);
			continue;
		}
		dis[v]=dis[u]+p.second;
		subtr[v]=subtr[u]?subtr[u]:v;
		dfs(v,u);
		sz[u]+=sz[v];SZ[u]+=SZ[v];
		if (mn[v]==mn[u]){
			s2[u]+=s2[v];
		}
	}
	tO[u]=timer;
}
void dfs2(int u,int fa,int s){
	if (dis[u]>=0){
		return;
	}
	C[u]+=s;
	for (auto p:to[u]){
		int v=p.first;
		if (v==fa||vis[v]){
			continue;
		}
		dfs2(v,u,s);
	}
}
void solve(int u,int n){
	getroot(u,0,n,u);root=u;
	dis[u]=subtr[u]=timer=0;
	dfs(u,0);
	tmp[u]=sz[u];tmp[0]=0;
	for (auto p:to[u]){
		int v=p.first;
		if (vis[v]){
			continue;
		}
		tmp[v]=sz[v];
		dfs2(v,u,SZ[u]-SZ[v]);
	}
	sort(vec.begin(),vec.end(),cmp);
	for (auto p:vec){
		int x=p.x,t=subtr[x];
		if (p.op){
			//query
			C[x]+=cnt[u]-cnt[t];
			S[x]+=sum[u]-sum[t];
//			cout<<"query "<<x<<endl;
			if (t){
//				ll s=SGT::val[1]-SGT::query(1,1,n,tI[t],tO[t]);
				S[x]+=(tmp[u]-tmp[t])*mx[x];
			}
		}
		else{
			//modify
			cnt[u]+=SZ[x];
			cnt[t]+=SZ[x];
//			ll s=SGT::query(1,1,n,tI[x],tO[x]);SGT::modify(1,1,n,tI[x],tO[x]);
			ll s=s2[x];
//			cout<<"modify "<<x<<' '<<s<<endl;
			sum[u]-=s*dis[x];sum[t]-=s*dis[x];
			tmp[u]-=s;tmp[t]-=s;
		}
	}
	vec.clear();
	vis[u]=1;
	cnt[u]=cnt[0]=sum[u]=sum[0]=0;
	for (auto p:to[u]){
		int v=p.first;
		if (vis[v]){
			continue;
		}
		sum[v]=cnt[v]=0;
		solve(v,sz[v]);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	mx[0]=-1;mn[0]=1;
	cin>>n;
	for (int u,v,w,i=1;i<n;++i){
		cin>>u>>v>>w;
		to[u].emplace_back(v,w);
		to[v].emplace_back(u,w);
	}
	tree::dfs(1,0);
	solve(1,n);
	cout<<1<<endl;
	for (int i=1;i<=n;++i){
		cout<<S[i]<<(" \n"[i==n]);
	}
	for (int i=1;i<=n;++i){
		cout<<C[i]<<(" \n"[i==n]);
	}
	return 0;
}

文章操作

相关推荐

评论

P12653 题解