loj#502. 「LibreOJ β Round」ZQC 的截图

离线做法显然 $dfs$  顺便开个桶记录下就好。

在线可以将桶换为主席树，一次增加 $log n$ 个点。被卡了

考虑非正解做法。

我们在 $mod 3$ 下运算的话，可以得到对于 3 个东西的判定。

1. $sum=0$ ，因为 $3kcdot cnt_1+3k cdot cnt_2 + ... equiv sum equiv 0 pmod{3}$。

2. 如果只有一个，不满足，那么 $3kcdot cnt_1+dk cdot cnt_2 + ... equiv sum pmod{3},d=1/2$，那么只要检验是否有一个的 $1/2$ 倍是整条路径权值和即可。

3. 显然。

增加正确率由于 $mod 3$，可以看做在 $3$ 进制下运算，多加几位即可。

找显然哈希表。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <ctime>

#define ll long long

using namespace std;
int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}
ll lrd() {
	ll f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

const int N=(int)(2e6+5),mod=10000007,W=36;
struct HASH {
	struct node {
		int uid,nex; ll val;
	}H[mod+2];
	int tot,head[mod+2];
	void clear() {
		tot=0; memset(head,0,sizeof(head));
	}
	int Find(ll v) {
		for(int i=head[v%mod];i;i=H[i].nex) if(H[i].val==v) return i;
		return -1;
	}
	int query(ll v) {
		int qwq=Find(v);
		if(~qwq) return H[qwq].uid;
		return -1;
	}
	void ins(ll v,int idd) {
		int qwq=Find(v);
		if(~qwq);
		else {
			H[++tot].uid=idd; H[tot].nex=head[v%mod]; H[tot].val=v; head[v%mod]=tot;
		}
	}
}Hash;

ll val[N],sum[N];
int n,m;

ll get_rand() {
	ll res=0;
	for(int i=0;i<W;i++) res=res*3+(rand()%3);
	return abs(res);
}

ll merge(ll x,ll y) {
	ll res=0,p=1;
	while(x||y) {
		res+=p*((x+y)%3);
		x/=3; y/=3; p*=3;
	}
	return res;
}

int main() {
	srand(19260817);
	n=rd(); m=rd();
	for(int i=1;i<=n;i++) {
		val[i]=get_rand(); Hash.ins(val[i],i); Hash.ins(merge(val[i],val[i]),i); //cout<<merge(val[i],val[i])<<endl;
		//cout<<val[i]<<endl; 
	}
	int ans=0,x,y;
	for(int i=1;i<=m;i++) {
		x=rd(); y=rd();
		x^=ans; y^=ans;
		sum[i]=merge(val[x],sum[y]); //cout<<sum[i]<<endl;//cout<<x<<" "<<y<<endl;
		if(!sum[i]) ans=-1;
		else {
			ans=Hash.query(sum[i]);
			if(ans==-1) ans=-2;
			//cout<<ans<<endl;
		}
		printf("%d
",ans);
	}
}