自动搬运

查看原文

来自洛谷，原作者为

	ZhongYuLin 天若有情天亦老，人间正道是沧桑

搬运于2025-08-24 22:46:51，当前版本为作者最后更新于2024-11-02 21:36:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么可持久化线段树合并能过啊。

树上邻域问题，考虑点分治。建出点分树，然后对于每个点提出子树内的所有点，前缀优化建边后双指针扫一轮（笔者的代码使用了暴力跳父亲加二分），可以 $O(n\log n)$ 建出转移图，然后做图上可达点统计即可，位运算优化转移可以做到 $O(\dfrac{n^2\log n}{w})$，其中 $w=64$。也就是每次取出 $64$ 个点进行状压，再拓扑排序。

听起来很简单？那你的代码能通过官方的完整数据吗？虽然纸面运算次数只有 $3\times10^9$，但是前缀优化建边自带 $2$ 倍常数，这就导致某个地方稍微常数大一点就过不了。包括但不限于：

1. 点分治写挂了，变成了大常数 $\log n$。

2. 内存访问不连续，这在暴力题中是致命的。

3. 前缀优化建图时建出了所有的虚点，而不是只建出需要的点。这会导致缩点后形成的分量过多，约为 $2$ 倍。

4. 图上转移时没有应用分量标号是逆拓扑序的性质，每次重新进行拓扑排序。

看起来只有内存访问不连续不好解决，因为其余的问题都指出了解决办法。经典的办法是进行边基排，优化十分显著。但此时笔者的代码最慢点要 $10$ 秒，仍然无法通过。问题出在哪里呢？

我们为什么只取 $64$ 个点啊，我缺这点空间？我取 $1024$ 个点状压，于是访问就比较连续了。

参考实现（并没有因为卡常而面目全非）：

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pli=pair<ll,int>;
using pii=pair<int,int>;
const int INF=0x3f3f3f3f;
const int N=1e5+3;
void ckmn(int &x,int y){if(y<x)x=y;}
struct Edge{int nxt,to;ll w;}e[N*100];
int head[N*35],dfn[N*35],dep[N],f[20][N],fa[N],sz[N],mx[N];
ll dis[N],R[N];
bitset<N*35>vis;
int tot,n,cnt,rt,sum;
void add(int u,int v,ll w=0){
	e[++tot]={head[u],v,w};
	head[u]=tot;
}
void dfs1(int x,int fa){
	f[0][++cnt]=fa;dep[x]=dep[fa]+1;
	dfn[x]=cnt;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa)continue;
		dis[y]=dis[x]+e[i].w;
		dfs1(y,x);
	}
}
int ckmx(int x,int y){return dep[x]<dep[y]?x:y;}
int lca(int x,int y){
	if(x==y)return x;
	if((x=dfn[x])>(y=dfn[y]))swap(x,y);
	int k=__lg(y-x);
	return ckmx(f[k][x+1],f[k][y-(1<<k)+1]);
}
ll calc(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];}
void getSz(int x,int f){
	sz[x]=1;mx[x]=0;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f||vis[y])continue;
		mx[x]=max(sz[y],mx[x]);
		getSz(y,x);sz[x]+=sz[y];
	}
}
void getRt(int x,int f){
	mx[x]=max(mx[x],sum-sz[x]);
	if(mx[x]<mx[rt])rt=x;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f||vis[y])continue;
		getRt(y,x);
	}
}
void solve(int x){
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(vis[y])continue;
		getSz(y,x);rt=0;sum=sz[y];
		getRt(y,x);fa[rt]=x;
		solve(rt);
	}
}
vector<pli>tmp[N];
vector<int>id[N];
void build(int x,int s){
	tmp[s].push_back({calc(x,s),x});
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		build(y,s);
	}
}
int st[N*35],bl[N*35],low[N*35];
int top,scc;
void tarjan(int x){
	st[++top]=x;vis[x]=1;
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y])tarjan(y),ckmn(low[x],low[y]);
		else if(vis[y])ckmn(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]&&++scc)
		while(1){
			int y=st[top--];
			bl[y]=scc;vis[y]=0;
			if(x==y)break;
		}
}
const int B=1<<10;
int ans[N],MX[N],LD[N*35],RD[N*35],to[N*100],bk[N*100];
vector<int>E[N*35];
bitset<B>g[N*35];
int main(){
	int u,v,x,y,z;ll w;
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>R[i];
	for(int i=1;i<n;++i)cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	dfs1(1,0);
	for(int j=1;1<<j<=n;++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			f[j][i]=ckmx(f[j-1][i],f[j-1][i+(1<<j-1)]);
	mx[0]=INF;getSz(1,0);sum=sz[1];getRt(1,0);solve(rt);
	fill_n(head+1,n,0);tot=0;
	int p=0;
	for(int i=1;i<=n;++i)
		if(fa[i])add(fa[i],i);
		else p=i;
	for(int i=1;i<=n;++i)build(i,i),sort(tmp[i].begin(),tmp[i].end());
	fill_n(head+1,n,0);tot=0;
	int now=n;fill_n(MX+1,n,-1);
	for(int i=1;i<=n;++i)
		for(int x=i;x;x=fa[x]){
			ll k=R[i]-calc(i,x);
			if(k<0)continue;
			int y=upper_bound(tmp[x].begin(),tmp[x].end(),make_pair(k,INF))-tmp[x].begin()-1;
			MX[x]=max(MX[x],y);
		}
	for(int x=1;x<=n;++x){
		if(tmp[x].empty()||MX[x]==-1)continue;
		int len=tmp[x].size();
		id[x].resize(MX[x]+1);
		add(id[x][0]=++now,x);
		for(int i=1;i<=MX[x];++i){
			add(id[x][i]=now+1,now);
			add(id[x][i]=++now,tmp[x][i].se);
		}
	}
	for(int i=1;i<=n;++i)
		for(int x=i;x;x=fa[x]){
			ll k=R[i]-calc(i,x);
			if(k<0)continue;
			int y=upper_bound(tmp[x].begin(),tmp[x].end(),make_pair(k,INF))-tmp[x].begin()-1;
			add(i,id[x][y]);
		}
	vis.reset();cnt=0;fill_n(dfn+1,n,0);
	for(int i=1;i<=now;++i)if(!dfn[i])tarjan(i);
	for(int x=1;x<=now;++x)
		for(int i=head[x];i;i=e[i].nxt)
			if((u=bl[x])!=(v=bl[e[i].to]))
				E[v].push_back(u);
	tot=0;
	for(int x=1;x<=scc;++x){
		sort(E[x].begin(),E[x].end());
		for(auto y:E[x])to[++tot]=y,bk[tot]=x;
	}
	for(int l=1,r;l<=n;l=r+1){
		r=min(l+B-1,n);memset(&g[1],0,128*scc);
		for(int i=l;i<=r;++i)g[bl[i]][i-l]=1;
		for(int i=1;i<=tot;++i)g[to[i]]|=g[bk[i]];
		for(int i=1;i<=n;++i)ans[i]+=g[bl[i]].count();
	}
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);puts("");
	return 0;
}