qoj10308 Utopiosphere 题解

考虑判定 \(G_1,G_2\) 等价，容易想到消环的过程中，最大边权对应的边必须一样，判定的充要条件就是所有点简单s环，最大边权的边相同。仙人掌启示我们考虑点双，仙人掌告诉我们一个点双中会有若干边等价，但是你肤浅了，因为你考虑改成一个 \(m\) 元不等式组，列一下容易发现限制是一棵树。比如考虑 \(E=\{(1,2,5),(1,3,4),(1,4,1),(2,5,3),(4,5,2)\}\)，此时将边视为重构树上的一个点，令边 \(e\) 的父亲为，覆盖 \(e\) 的所有边简单环中最大边权对应的 \(e_1\) 中，\(w_{e_1}>w_e\) 且 \(w_{e_1}\) 最小的 \(e_1\)，如果 \(e\) 是覆盖所有边简单环中最大边权的，那么 \(e\) 就是一个根节点，如果 \(e\) 是割边那么就是一个孤立点。

令这个重构树为 \(T\)，你发现答案就是 \(T\) 的拓扑序个数，而森林的拓扑序是很容易计算的，最终答案就是 \(m!\) 除以所有子树大小的乘积。

问题在于求出 \(T\)。其实容易想到按照边权从小到大加入边（因为从大到小删除疑似不太有救），而边简单环具体长什么样并不需要关心，我们只需要关心 \(e_1,e_2\) 是否可以通过一个点简单环串起来。\(e\) 的父亲的寻找变为：每次加入一条边 \(e_1\)，考虑所有未被标记的 \(e\)，如果 \(e,e_1\) 满足前述条件，则对 \(e\) 标记并令 \(fa_e\to e_1\)。你发现这一步事实上就是在维护点双，可以圆方树左。标记的话，将这个东西挂在点双上，每个点双维护待选集合。直接维护圆方树，变为以下的问题：动态维护一个森林，每次 \(\text{link}(u,v)\)，或者将 \(u,v\) 路径缩成一个点。但其实缩树之前的样子就是一个最小生成树的边有用，所以先把这个求出来，然后暴力缩路径就是容易的。使用并查集维护最小生成树的求解以及圆方树路径缩点的操作，使用一个并查集维护方点的合并即可。时间复杂度 \(\mathcal O(n\alpha(n))\)。

代码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) ((x)&(-(x)))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
void fre(){
	// freopen("xxx.in","r",stdin),freopen("xxx.out","w",stdout);
}
bool ST;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); } 
const int maxn=400005,mod=998244353;
inline int qpow(int x,ll y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod; return res; }
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
int fac[maxn],ifac[maxn],inv[maxn];
void init(const int N){
	fac[0]=ifac[0]=inv[0]=1;
	F(i,1,N)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N]=qpow(fac[N],mod-2);
	dF(i,N-1,1)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	F(i,1,N)inv[i]=1ll*ifac[i]*fac[i-1]%mod;
}
int n,m;
struct DSU{
	int fa[maxn];
	void init(){ F(i,1,maxn-3)fa[i]=i; }
	int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
	void mrg(int x,int y){ x=find(x),y=find(y); if(x^y)fa[x]=y; }
}t1,t2;
pii rev[maxn];
vector<int>e[maxn],g[maxn];
int anc[maxn],dep[maxn],frm[maxn];
map<pii,int>mp,mp1;
#define minmax(x,y) mkp(min(x,y),max(x,y))
void init_dfs(int u){
	for(int v:e[u])if(v^anc[u])dep[v]=dep[u]+1,anc[v]=u,init_dfs(v);
}
int lca(int u,int v){
	u=t2.find(u),v=t2.find(v);
	while(u!=v){
		if(dep[u]>dep[v])u=anc[t2.find(u)];
		else v=anc[t2.find(v)];
	}
	return u;
}
int siz[maxn];
int dfs1(int u){
	int res=1;
	siz[u]=1;
	for(int v:g[u])res=1ll*res*dfs1(v)%mod,siz[u]+=siz[v];
	res=1ll*res*inv[siz[u]]%mod;
	return res;
}
int S[maxn];
void Solve_(){
	cin>>n>>m;
	F(_,1,m){ int u,v,w;cin>>u>>v>>w,rev[w]=mkp(u,v); }
	t1.init();
	int cnt=n;
	F(w,1,m){
		const auto[u,v]=rev[w];
		int x=t1.find(u),y=t1.find(v);
		if(x==y)continue;
		t1.mrg(x,y),++cnt,mp[minmax(u,v)]=cnt;
		e[u].push_back(cnt),e[cnt].push_back(u);
		e[v].push_back(cnt),e[cnt].push_back(v);
	}
	F(i,1,n)if(!anc[i])init_dfs(i);
	t1.init(),t2.init();
	F(i,1,n)t2.fa[i]=anc[i];
	F(w,1,m){
		auto[u,v]=rev[w];
		int x=t1.find(u),y=t1.find(v);
		if(x!=y)t1.mrg(x,y),S[mp[minmax(u,v)]]=w;
		else{
			vector<int>V;
			while(u!=v){
				if(dep[u]>dep[v])V.push_back(t2.find(u)),u=anc[t2.find(u)];
				else V.push_back(t2.find(v)),v=anc[t2.find(v)];
			}
			++cnt,t2.fa[cnt]=cnt;
			for(int i:V)if(S[i])frm[S[i]]=w,S[i]=0;
			for(int i:V)t2.mrg(i,cnt);
			anc[cnt]=u,S[cnt]=w;
		}
	}
	F(i,1,m)if(frm[i])g[frm[i]].push_back(i);
	int ans=fac[m];
	F(i,1,m)if(!frm[i])ans=1ll*ans*dfs1(i)%mod;
	cout<<ans<<'\n';
}
bool ED;
signed main(){
	init(maxn-3);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	fre(); int zsy=1;
	F(i,1,zsy)Solve_();
	cerr<<"time used: "<<(double)clock()/CLOCKS_PER_SEC<<endl;
	cerr<<"memory used: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB"<<endl;
}
// g++ qoj10308.cpp -o a -std=c++14 -O2