[传智杯 #4 决赛] 生活在树上(easy version)
题目背景
本题是 P8201 的简单版本,两道题目的解法略有不同。本题和 P8201 在题意上的区别在于本题给定树上的边权,而不是点权。
小智生活在「传智国」,这是一个有 $n$ 个城市的国家,各个城市由 $n-1$ 条道路相连。
每个道路都有长度 $w_i$ ,我们定义,小智从城市 $a$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{a, b} = \bigoplus \limits_{e \in \mathrm{path}\left(a, b\right)} w_e$,其中 $\bigoplus$ 表示按位异或(如果你不知道什么是按位异或,请参见题目下方的提示/说明),$\mathrm{path}\left(a,b\right)$ 表示 $a$ 到 $b$ 的简单路径上的边集。也即 $\mathrm{dis}_{a, b}$ 表示将 $a$ 与 $b$ 的简单路径上所有边写作 $e_1, e_2, e_3, \dots$ 后,求 $w_{e_1} \bigoplus w_{e_2}\bigoplus w_{e_3} \dots$ 的结果。
有一天,小智获得了去参加传智杯的机会,他在前往比赛地的路上想到了一个问题,但他好像不会做,于是他把这个题告诉了你。聪明的同学,你可以帮帮他吗?
题目描述
小智说:「由于我们的国家只有 $n$ 个城市和 $n-1$ 条道路,那么我们的国家就相当于是一棵树。我在想,在我们的国家中,是否有城市满足『到城市 $a$ 的代价和到城市 $b$ 的代价的异或等于 $k$』。好难哦,我想不出来,你能帮帮我吗?」
也就是说,给定城市 $a, b$ 和整数 $k$,请你计算是否存在城市 $t$ 满足 $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$。
输入格式
第一行有两个整数 $n$,$m$,表示国家的城市数和询问的个数。
接下来 $n-1$ 行,每行有两个整数 $x, y, l$,表示城市 $x$ 与城市 $y$ 有一条长度为 $l$ 的边。
接下来 $m$ 行,每行有三个整数 $a, b, k$,表示小智从城市 $a$ 走到城市 $b$,$k$ 的含义与题目描述一致。
输出格式
共 $m$ 行,每行一个整数。
对于第 $i$ 个询问,如果存在至少一个城市 $t$ 满足要求,则输出 Yes
。
如果不存在任何一个城市满足条件,则输出 No
。
输出字符串大小写不敏感,例如,Yes
、yES
、YES
、yes
等都算作 Yes
。
样例 #1
样例输入 #1
5 3
1 2 2
1 3 6
2 4 8
2 5 1
1 2 4
2 3 12
1 4 10
样例输出 #1
nO
No
YeS
样例 #2
样例输入 #2
5 10
2 1 63
3 1 57
4 2 2
5 2 84
5 2 84
4 1 9977404983223574764
2 5 84
2 1 15996060349666123522
5 4 86
3 1 8428615422876116375
5 1 107
2 3 6
2 3 6
4 2 2
样例输出 #2
yeS
nO
YEs
No
YEs
nO
YEs
yeS
yeS
YEs
提示
相关概念解释
「树」:树是一个有 $n$ 个结点和 $n-1$ 条边的无向简单连通图。
「按位异或」:按位异或即 C++、python、java 语言中的 「^」 运算。它是一个二元运算,步骤是将两个数的二进制位按位比较,相同为 $0$,不同为 $1$。例如:$3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$。请注意,这是一个按位运算,不是一个逻辑运算。
样例 1 解释
下图为传智国的地图。
$\forall t \in \{1, 2, 3, 4, 5\}$,都不可能有 $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$,$\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$,于是输出 No
;
而取 $t = 5$,有 $\mathrm{dis}_{t, 1} \bigoplus \mathrm{dis}_{t, 4} = 10$,于是输出 Yes
。
数据规模与约定
对于所有测试点,保证 $1 < n \leq 5 \times 10^5$,$1 \leq m \leq 5 \times 10^5$,$0 \leq w_i < 2^{64}$。
对于每次询问,保证 $1 \leq a, b \leq n$ 且 $a \neq b$,$0 \leq k < 2^{64}$。
题目分析
首先这里的距离$dist$有特殊的定义,就是路径长是异或得到的
那我们知道异或有很多性质,比如
$a \bigoplus \mathrm a = 0$
$a \bigoplus \mathrm b = b \bigoplus \mathrm a$
$a \bigoplus \mathrm x = c \rightarrow a \bigoplus \mathrm c = x$
…
那我们不妨假设一下
要知道$a$到$b$路径上是否存在点$c$,使得$\mathrm{dis}_{c, a} \bigoplus \mathrm{dis}_{c, b} = k$
从$c$到$a$需要经过$x_1 , x_2 , … , x_{i - 1}$ , $c$为$x_0$ , $a$为$x_i$
从城市 $c$ 走到城市 $a$ 的代价是 $\mathrm{dis}_{c, a} = \bigoplus \limits_{\mathrm{i} = c \rightarrow a} {dis}_{x_i , x_{i + 1}}$
从$c$到$b$需要经过$y_1 , y_2 , … , y_{j - 1}$, $c$为$y_0$ , $b$为$y_j$
从城市 $c$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{c, b} = \bigoplus \limits_{\mathrm{j} = c \rightarrow b} {dis}_{y_j , y_{j + 1}}$
那么结果就是 ${dis}_{c, a} \bigoplus \mathrm {dis}_{c, b}$
由于异或有交换律,所以我们可以发现,任取路径上的一点,我们得到的答案是一样的,因此,为了方便,我们直接计算所有节点到根节点的$dist$值即可
如果满足条件就是${dis}_{1, a} \bigoplus \mathrm {dis}_{1, b} = k$
这里还存在一件事,就是如果从$a$到$b$不需要经过根怎么办
换句话说$a$和$b$的最近公共祖先不是根节点是否影响结果
可以发现就算不经过根节点,但是我们从根节点绕一下的路径中,两者一定含有重合,再通过异或的性质$a \bigoplus \mathrm a = 0$,重合部分异或完的结果为$0$,所以不影响结果,也就不影响答案
求$dist$值用$bfs$和$dfs$均可
代码
1.$bfs$ $O(n)$
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 500010, M = 2 * N;
int T;
int n, m;
int e[M], ne[M], w[M], idx, h[N];
bool st[N];
int dist[N]; // 到根的异或距离(dist)
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void bfs(int u)
{
st[u] = true;
queue<int> q;
q.push(u);
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (st[j])
continue;
st[j] = true;
dist[j] = dist[t] ^ w[i];
q.push(j);
}
}
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
memset(dist, 0, sizeof dist);
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
bfs(1); // 遍历整棵树求出dist
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
if ((dist[a] ^ dist[b]) == c)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}
2.$dfs$ $O(n)$
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 500010, M = 2 * N;
int T;
int n, m;
int e[M], ne[M], w[M], idx, h[N];
bool st[N];
int dist[N]; // 到根的异或距离(dist)
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
if (st[u])
return;
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dist[j] = dist[u] ^ w[i];
dfs(j);
}
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
memset(dist, 0, sizeof dist);
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dfs(1); // 遍历整棵树求出dist
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
if ((dist[a] ^ dist[b]) == c)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin >> T;
T = 1;
while (T--)
{
solve();
}
return 0;
}