[传智杯 #4 决赛] [yLOI2021] 生活在树上(hard version)
题目背景
本题是 P8200 的较难版本,两道题目的解法略有不同。本题和 P8200 在题意上的区别在于本题给定树上的点权,而不是边权。
小智生活在「传智国」,这是一个有 $n$ 个城市的国家,各个城市由 $n-1$ 条道路相连。
每个城市都有一个财富指数 $w_i$ ,我们定义,小智从城市 $a$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{a, b} = \bigoplus \limits_{u \in \mathrm{path}\left(a, b\right)} w_u$,其中 $\bigoplus$ 表示按位异或(如果你不知道什么是按位异或,请参见题目下方的提示/说明),$\mathrm{path}\left(a,b\right)$ 表示 $a$ 到 $b$ 的简单路径上的点集(包括 $a$ 和 $b$)。也即 $\mathrm{dis}_{a, b}$ 表示将 $a$ 与 $b$ 的简单路径上所有点写作 $u_1, u_2, u_3, \dots$ 后,求 $w_{u_1} \bigoplus w_{u_2}\bigoplus w_{u_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$ 个整数 $w_i$,表示 $i$ 号城市的财富指数。
接下来 $n-1$ 行,每行有两个整数 $x, y$,表示城市 $x$ 与城市 $y$ 有一条边相连。
接下来 $m$ 行,每行有三个整数 $a, b, k$,表示小智从城市 $a$ 走到城市 $b$,$k$ 的含义与题目描述一致。
输出格式
输出共 $m$ 行。
对于第 $i$ 个询问,如果存在至少一个城市 $t$ 满足要求,则输出 Yes
。
如果不存在任何一个城市满足条件,则输出 No
。
输出字符串大小写不敏感,例如,Yes
、yES
、YES
、yes
等都算作 Yes
。
样例 #1
样例输入 #1
5 3
2 6 8 1 5
1 2
1 3
2 4
2 5
1 2 4
2 3 12
2 3 10
样例输出 #1
nO
No
YeS
样例 #2
样例输入 #2
5 10
93 97 100 93 93
2 1
3 2
4 3
5 1
5 2 93
4 1 93
3 2 100
3 2 100
2 3 9999998
1 2 93
2 3 97
1 2 93
2 3 97
4 3 93
样例输出 #2
no
nO
yEs
yEs
No
yEs
yeS
YES
yES
yes
提示
相关概念解释
「树」:树是一个有 $n$ 个结点和 $n-1$ 条边的无向简单连通图。
「按位异或」:按位异或是一个二元运算,步骤是将两个数的二进制位按位比较,相同为 $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=4$,有 $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 10$,于是输出 Yes
。
数据规模与约定
对于所有测试点,保证 $1 < n \leq 5 \times 10^5$,$1 \leq m \leq 5 \times 10^5$,$0 \leq w_i \leq 1\times 10^7$。
对于每次询问,保证 $1 \leq a,b \leq n$ 且 $a \neq b$,$0 \leq k \leq 1\times 10^7$。
提示
- 请注意常数因子对程序效率造成的影响。
- 对于两个 $x, y \leq 10^7$,$x \bigoplus y$ 可能大于 $10^7$,请特别注意这一点。
题目分析
这道题跟easy version的区别就在于,一个是点权,一个是边权
再看easy version的思路中存在偏差的地方
这里还存在一件事,就是如果从$a$到$b$不需要经过根怎么办
换句话说$a$和$b$的最近公共祖先不是根节点是否影响结果
可以发现就算不经过根节点,但是我们从根节点绕一下的路径中,两者一定含有重合,再通过异或的性质$a \bigoplus \mathrm a = 0$,重合部分异或完的结果为$0$,所以不影响结果,也就不影响答案
现在我们分别考虑两种情况,第一种是选择$a \rightarrow b$路径之中的点,第二种是选择$a \rightarrow b$路径之外的点。
- 如果我们选择路径之中的点,那么两个路径异或的答案为路径上除选择的该点外所有点异或的值
- 如果我们选择路径之外的点,那么两个路径异或的答案为路径上除了三者中任意两者的最近公共祖先之外所有点异或的值
那么其实就是在路径上任选一点
现在我们来考虑$a \rightarrow b$的路径长度问题
在easy version中,我们不需要去考虑重复的那部分影响,因为重复的边权异或后会消$0$,所以我们的距离直接计算每一点到根节点的距离即可。但是在点权中就不行了,因为在两者到根节点的路径中,重合的点包含他们两的最近公共祖先,而这个最近公共祖先是存在在他们路径之中的,需要异或到答案中,如果按照边权的思路来的话,这个点的点权会重复,异或成$0$。因此,我们需要找到$a$和$b$的最近公共祖先,将原先的答案再异或上$lca(a , b)$的点值即可
求$lca(a , b)$我们用到的是$tarjan$离线求法,时间复杂度为$O(n)$
现在问题就转化为了:$(x,y)$ 上是否存在点 $t$,满足$w_t = W = {dist}_x \bigoplus {dist}_y \bigoplus w_{lca} \bigoplus k$。
我们只需要查询 $(x,a)$ 和 $(y,b)$ 两条链上其个数然后相加即可,其中 $b$ 是$a$ 的「是$y$的祖先的」孩子。我们只需要在$x,y,a,fa(a)$四个点分别打上查询标记,查询这四个位置到根的路径上 $W$ 的权值个数,记为 $p$,则 $(x,y)$ 上$W$ 权值个数即为$p_x + p_y − p_a − p_{fa(a)}$ 。
统计$p$ 只需要用树上差分的套路,离线询问,在树上打标记,最后进行一次$dfs$,用一个全局桶维护当前节点到根的权值数量即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010, M = 20000010;
int T;
typedef pair<int, int> PII;
int n, m;
int h[N], e[N * 2], w[N], ne[N * 2], idx; // 双向边
int dist[N];
int p[N], f[N];
int res[N], k[N];
int st[N];
int a[N], b[N], lca[N];
vector<PII> query[N]; // first存查询的另外一个点,second存查询编号
struct path
{
int id, W, f;
};
vector<path> q[N];
int ans[N];
int W[M];
void calc(int u, int f)
{
W[w[u]]++;
for (path it : q[u])
ans[it.id] += W[it.W] * it.f;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == f)
continue;
calc(j, u);
}
W[w[u]]--;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{
f[u] = fa;
dist[u] = w[u] ^ dist[fa];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
dfs(j, u);
}
}
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
tarjan(j);
p[j] = u;
}
}
for (auto item : query[u])
{
int y = item.first, id = item.second;
if (st[y] == 2)
{
int LCA = find(y);
res[id] = dist[u] ^ dist[y] ^ w[LCA];
lca[id] = LCA;
}
}
st[u] = 2;
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
for (int i = 0; i < m; i++)
{
cin >> a[i] >> b[i] >> k[i];
query[a[i]].push_back({b[i], i});
query[b[i]].push_back({a[i], i});
}
for (int i = 1; i <= n; i++)
p[i] = i;
dfs(1, -1);
tarjan(1);
for (int i = 0; i < m; i++)
{
int W = res[i] ^ k[i];
q[a[i]].push_back((path){i, W, 1});
q[b[i]].push_back((path){i, W, 1});
q[lca[i]].push_back((path){i, W, -1});
q[f[lca[i]]].push_back((path){i, W, -1});
}
calc(1, -1);
for (int i = 0; i < m; i++)
cout << (ans[i] ? "Yes" : "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;
}