UOJ #155. 【清华集训2015】遥远的星系

首先考虑结论：\(u\) 和 \(v\) 必须在同一个联通分量里面，然后从 \(u\) 沿任意路径走到 \(v\) ，设剩下的时间为 \(t\) ，若 \(t\) 是当前联通分量中所有环的长度的 \(\gcd\) 的倍数，那么答案是 \(1\) ，否则是 \(0\) 。

对于其正确性：若存在满足条件的路径，必定是通过一条链，并路过几个环。由于边正反走的权值互为相反数，那么可以做到经过任意一个环，又由于裴蜀定理那套理论，所以结论是正确的。

然后可以维护并查集，并记录 \(u\) 与 \(fa_u\) 之间的边权 \(dis_u\)，\(fa_u\) 指并查集上的 \(fa\)，并在路径压缩的时候动态更改，那么每次查询的时候可以得到一个点到根的路径。同时可以发现 \(u\) 和 \(v\) 之间实际的距离就是 \(dis_u-dis_v\) ，并在连边的时候做到快速更新。

Code:

// namespace maze_io
#define N 100005
int fa[N],n,Q,k,t;
ll ans[N],dis[N];
int find(int u)
{
	if(fa[u]==u) return u;
	int tmp=fa[u];
	fa[u]=find(fa[u]);
	dis[u]+=dis[tmp];
	return fa[u];
}
ll gcd(ll x,ll y)
{
	return y==0?x:gcd(y,x%y);
}
signed main()
{
	maze_io::get_args(&n,&Q,&k,&t);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int _=1;_<=Q;_++)
	{
		int opt,u,v; ll w;
		maze_io::get_line(&opt,&u,&v,&w);
		if(!opt)
		{
			int U=find(u),V=find(v);
			if(U==V)
			{
				ll R=dis[u]-dis[v]-w;
				ans[U]=gcd(ans[U],abs(R));
			}
			else
			{
				fa[U]=V;
				dis[U]=dis[v]+w-dis[u];
				ans[V]=gcd(ans[U],ans[V]);
			}
		}
		else
		{
			int U=find(u),V=find(v);
			if(U!=V) maze_io::put_ans(0);
			else
			{
				ll R=abs(w-dis[u]+dis[v]);
				if(ans[V]==0) maze_io::put_ans(R==0);
				else maze_io::put_ans(R%ans[V]==0);
			}
		}
	}
	return 0;
}