自动搬运

查看原文

来自洛谷，原作者为

	AC_CSP AFO.

搬运于2025-08-24 22:44:09，当前版本为作者最后更新于2022-12-25 12:42:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一个显而易见的性质：$\text{dis}(i,j)=\text{dis}(i,k)\oplus \text{dis}(j,k)(i,j,k\in[1,n])$。

下面给出证明：

设 $s$ 为 $i\to k$ 的路径与 $j\to k$ 的路径上第一个重合的点。

$\therefore \text{dis}(i,k)=\text{dis}(i,s)\oplus \text{dis}(s,k),\text{dis}(j,k)=\text{dis}(j,s)\oplus \text{dis}(s,k)$。

$\therefore \text{dis}(i,k)\oplus \text{dis}(j,k)=\text{dis}(i,s)\oplus \text{dis}(s,k)\oplus \text{dis}(j,s)\oplus \text{dis}(s,k)=\text{dis}(i,s)\oplus\text{dis}(j,s)=\text{dis}(i,j)$。

不妨任选一点 $x(1\le x\le n)$ 出发，预处理出所有 $\text{dis}(i,x)(1\le i\le n)$。时间复杂度 $\mathcal{O}(n)$。

现在我们来观察 $\displaystyle\bigoplus\limits_{i=l}^r (\text{dis}(i,x) \oplus \text{dis}(i,y))$。

由上文的性质可得，$\text{dis}(i,x)\oplus\text{dis}(i,y)=\text{dis}(x,y)$。

也就是说，$\displaystyle\bigoplus\limits_{i=l}^r (\text{dis}(i,x) \oplus \text{dis}(i,y))=\displaystyle\bigoplus\limits_{i=l}^r \text{dis}(x,y)$。

又因为 $\text{dis}(x,y)\oplus\text{dis}(x,y)=0$，所以我们讨论 $r-l+1$ 的奇偶性即可。时间复杂度 $\mathcal{O}(q)$。

总时间复杂度 $\mathcal{O}(n+q)$。

$\text{Code}$：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
struct edge{
	int nxt,v,w;
}e[N<<1];
int h[N],cnt;
inline void add_edge(int u,int v,int w){
	e[++cnt].nxt=h[u],e[cnt].v=v,e[cnt].w=w;
	h[u]=cnt;
}
int n,q;
int x,y,l,r;
int dis[N];
inline int read(){
	int sum=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
	return sum;
}
inline void dfs(int u,int fa){
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		dis[v]=dis[u]^w;
		dfs(v,u);
	}
}
inline void write(int x){
	if(x/10) write(x/10);
	putchar(x%10^48);
}
signed main(){
	//freopen("10.in","r",stdin);
	//freopen("10.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w),add_edge(v,u,w);
	}
	dfs(1,0);
	for(int i=1;i<=q;i++){
		x=read(),y=read(),l=read(),r=read();
		write(r-l+1&1?dis[x]^dis[y]:0),putchar('\n');
	}
	return 0;
}