自动搬运

查看原文

来自洛谷，原作者为

	I_am_Accepted 我的心脏不再跳动了。

搬运于2025-08-24 22:53:38，当前版本为作者最后更新于2023-12-24 22:32:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

按边的出现顺序建 Kruskal 重构树，一条边连接两个连通块对一个点的答案会发生：先走完其连通块内的所有边，再走这条边，再以这条边的端点为起点走另一个连通块。

也就是这个点更新后的答案为原先答案、这条边、对面端点答案三者顺次拼接。

发现把 Kruskal 树平摊后就是线段树维护区间加乘。

复杂度 $O(n\log n)$，赛时写的这个。

但是我们可以更简单一点，Kruskal 树构建的时候并查集我们带上权值，代表加乘 tag，操作顺序从底向上，此信息支持路径压缩。

这样在一条边连接两个连通块时先得到两个端点的答案，再用这两个值求出并查集两条边的边权即可。

这里能用并查集的原因是打 tag 都是对 Kruskal 树的整棵子树打 tag（所以平摊到序列强化了问题），而且顺序是由叶子向根（平摊到序列则被包含的区间 tag 时刻一定在包含的之前）。

并查集复杂度。

using Z=mod_int<P>;
const int N=200010;
int f[N<<1],sz[N<<1],tot,n,m;
Z pw[N];
struct node{
	Z mul,ad;
	node operator+(const node&v)const{ return node{mul*v.mul,ad*v.mul+v.ad}; }
}g[N<<1];
void gf(int x){
	if(x==f[x]) return ;
	gf(f[x]);
	g[x]=g[x]+g[f[x]];
	f[x]=f[f[x]];
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>m;
    tot=n;
    pw[0]=1;
    rep(i,1,n) pw[i]=pw[i-1]*10;
    iota(f+1,f+2*n,1);
    fill(g+1,g+2*n,node{1,0});
    rep(i,1,m){
    	int x,y;
    	cin>>x>>y;
    	gf(x),gf(y);
    	if(f[x]!=f[y]){
    		node xx=g[x],yy=g[y],zz={10,i};
    		g[f[x]]=zz+yy;
    		g[f[y]]=zz+xx;
    		f[f[x]]=f[f[y]]=++tot;
    	}
    }
    rep(i,1,n){
    	gf(i);
    	cout<<g[i].ad<<"\n";
    }
return 0;}