这个东西没题解？

这题细节还不少，不愧是老省选题。
看到题面，发现每条边相当于

的限制，这像一个带权并查集的形式。
但是，这破玩意难写、难调（本人写+调 $4000+$ 秒未果）。
突然发现，所有边加入后才查询，因此完全可以把并查集换为DFS。
注意事项：

• 记得特判负号！
• 图不保证连通！
• 多次测试要彻底清空！

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p[26]={998244353,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};//预处理质数表，节省时间
int t,n,m,x,y,a,b,ans,g[1007],f[1007][27];
vector<int>v[1007];//边连向哪里
vector<int>w[1007][2];//边权
void DFS(int x){
	for(int i=0;i<v[x].size();i++){
		if(!ans) return;
		int y=v[x][i],a=w[x][0][i],b=w[x][1][i],e=0;//降低码量，方便调试
		if(a*b<0) e=1;
		if(g[y]){
			if(((f[x][0]^f[y][0])&1)!=e) ans=0;//特判负号
			for(int j=1;j<=25;j++){
                //对每个质数分别处理权值
				int z=f[x][j]-f[y][j];
				while(a%p[j]==0){
					a/=p[j];
					z--;
				}
				while(b%p[j]==0){
					b/=p[j];
					z++;
				}
				if(z) ans=0;
			}
			if(!ans) return;
			continue;
		}
		for(int j=0;j<=25;j++) f[y][j]=f[x][j];
        //同上
		f[y][0]+=e;
		for(int j=1;j<=25;j++){
			while(a%p[j]==0){
				a/=p[j];
				f[y][j]--;
			}
			while(b%p[j]==0){
				b/=p[j];
				f[y][j]++;
			}
		}
        //不要漏了下面2行！
		g[y]=1;
		DFS(y);
	}
	return;
}
int main(){
	cin>>t;
	for(int h=1;h<=t;h++){
		cin>>n>>m;
		ans=1;
        //警钟长鸣：多测一定要清空！
		for(int i=1;i<=n;i++){
			for(int j=0;j<=25;j++) f[i][j]=0;
			g[i]=0;
			v[i].clear();
			w[i][0].clear();
			w[i][1].clear();
		}
		for(int i=1;i<=m;i++){
			cin>>x>>y>>a>>b;
			v[x].push_back(y);
			w[x][0].push_back(a);
			w[x][1].push_back(b);
			v[y].push_back(x);
			w[y][0].push_back(b);
			w[y][1].push_back(a);
		}
		for(int i=1;i<=n;i++){
			if(!g[i]){
				g[i]=1;
				DFS(i);
			}
		}
		cout<<"Case #"<<h<<": ";
		if(ans) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
        //破题，输出格式这么麻烦
	}
	return 0;
}