Solution

赛时竟然不会这种萌萌题。

考虑每个时刻，集合 $S$ 必然是一个连通块，而且这个连通块必然在对整个图跑 Kruskal 求最小生成树的过程中出现过。

换句话说，我们实际上就是对整个图进行 Kruskal，然后每次合并两个连通块 $S_1$ 和 $S_2$，考虑 $u \in S_1$，他的过程实际上是这样的：

1. 在自身连通块 $S_1$ 中发育。在他填满 $S_1$ 之前，他不会找 $S_1$ 外的一个点，否则在进行 Kruskal 的过程中那个点与 $S_1$ 连的边会更早被考虑。
2. 发育到 $S_2$ 中。我们惊奇的发现，所有的 $u$ 他接触的第一个 $S_2$ 中的节点都是一样的，我们设为 $v$。
3. 在 $S_2$ 中发育。和第一种情况类似，接下来我们会从 $v$ 开始往后发育。而这样的发育过程必定和 $v$ 最开始发育的过程是一样的，原因依旧是 $S_1$ 到 $S_2$ 所有点的边都比 $v$ 到他们的小，因此可以直接利用 $v$ 的答案。

于是 $u$ 中每个点的答案会变成 $ans'_u=(10ans_u+id) \times 10^{|S_2|-1} + ans_v$。

然后你发现你只需要能维护一大堆东西乘、加、单点查询。用 Kruskal 重构树把它变成连续段就可以用线段树 2 了。

为啥用发育这个词。因为我觉得这个过程，很像，generals。

好像是最劣解（截止 2023-12-29）。无所谓，反正人傻常数大。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--) 
using namespace std;
const int MAXN=4e5+10,MAXM=4e5+10,MOD=1e9+7;
int n,m,pw[MAXN],sze[MAXN],u[MAXM],v[MAXM],fa[MAXN],lson[MAXM],rson[MAXM],rt[MAXN],tot,dfn[MAXN],cnt,lid[MAXN],rid[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
void dfs(int u) {
	if(u<=n) return dfn[u]=++cnt,void();	
	dfs(lson[u]),dfs(rson[u]);
	return ;
}
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
int res[MAXN<<2],mul[MAXN<<2],add[MAXN<<2];
void add_tag(int k,int l,int r,int Mul,int Add) {
	res[k]=(res[k]*Mul%MOD+(r-l+1)*Add%MOD)%MOD;
	mul[k]=mul[k]*Mul%MOD;
	add[k]=(add[k]*Mul+Add)%MOD;
	return ;
}
void push_down(int k,int l,int r) {
	add_tag(lson,l,mid,mul[k],add[k]),add_tag(rson,mid+1,r,mul[k],add[k]);
	mul[k]=1,add[k]=0;
	return ;	
}
void update(int k,int l,int r,int x,int y,int Mul,int Add) {
	if(x<=l&&r<=y) return add_tag(k,l,r,Mul,Add),void();
	push_down(k,l,r);
	if(x<=mid) update(lson,l,mid,x,y,Mul,Add);
	if(y>mid) update(rson,mid+1,r,x,y,Mul,Add);
	res[k]=(res[lson]+res[rson])%MOD;
	return ;
}
int query(int k,int l,int r,int pos) {
	if(l==r) return res[k];
	push_down(k,l,r);
	if(pos<=mid) return query(lson,l,mid,pos);
	return query(rson,mid+1,r,pos);	
}
#undef lson
#undef rson
#undef mid
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m; ffor(i,1,n) fa[i]=i,rt[i]=i; tot=n;
	pw[0]=1; ffor(i,1,n) pw[i]=pw[i-1]*10%MOD;
	ffor(i,1,m) cin>>u[i]>>v[i];
	ffor(i,1,m) if(find(u[i])!=find(v[i])) {
		int U=find(u[i]),V=find(v[i]);
		++tot,lson[tot]=rt[U],rson[tot]=rt[V],fa[V]=U,rt[U]=tot;	
	}
	dfs(tot);
	ffor(i,1,(n<<2)) mul[i]=1;
	ffor(i,1,n) fa[i]=i,sze[i]=1,lid[i]=rid[i]=dfn[i];
	ffor(i,1,m) if(find(u[i])!=find(v[i])) {
		int U=find(u[i]),V=find(v[i]);
		int oril=query(1,1,n,dfn[u[i]]),orir=query(1,1,n,dfn[v[i]]);
		update(1,1,n,min(lid[U],lid[U]),max(rid[U],rid[V]),10,i);
		update(1,1,n,lid[U],rid[U],pw[sze[V]-1],orir);
		update(1,1,n,lid[V],rid[V],pw[sze[U]-1],oril);
		fa[V]=U,lid[U]=min(lid[U],lid[V]),rid[U]=max(rid[U],rid[V]),sze[U]+=sze[V];
	}
	ffor(i,1,n) cout<<query(1,1,n,dfn[i])<<'\n';
	return 0;
}