坠梦 | Falling into Dream 题解
AC_CSP
·
·
题解
有一个显而易见的性质：\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)\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}$：
```cpp
#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;
}
```