P8201

一扶苏一 · 2022-03-12 20:39:25 · 题解

题外话，比赛时大家好像都在树剖，没见到几个写差分的（（这题不会成了天天爱跑步 2.0 吧（

F2. 生活在树上（hard version）

题意：给定一棵树，点数为 n，点有点权。定义树上两点间路径的权值是其简单路径上点权的异或和。有 q 次询问，每次给定两个节点 x, y 查询是否存在一个点 u，使 u 到 x 和 u 到 y 的路径的权值的异或为 k。

关键词：前缀和，构造，树上差分。

参考难度：绿。

分析：首先异或构成一个 Abel 群，所以如果一个点在 u 到 x 和 y 的路径上都出现了，那么他对答案没有贡献。

考虑 u 到 x 的路径和 u 到 y 的路径总是先经过若干个相同的点，然后与 (x, y) 所成的链有一个交点 t，接着在这个交点处分开，一个走向 x 一个走向 y，如图：

图中红色路径是 u 到 x 的路径，蓝色路径是 u 到 y 的路径，二者在 (u, t) 部分是重复的。不难验证，无论 u 在哪个位置，都满足这个性质。

于是我们发现，\mathrm{dis}_{u, x} \bigoplus \mathrm{dis}_{u, y} 的值可能是 s_x \bigoplus s_y \bigoplus w_a \bigoplus w_t，s_x 和 s_y 表示 x，y 到根路径的点权异或和，t 是 x 到 y 的链上任何一个点，a 是 x 和 y 的最近公共祖先。注意到 a 在链上，但是 w_a 在 s_x 和 s_y 中都被计算了一次，二者的异或没有了 w_a 的贡献，因此要再异或一次把贡献加回来；此外考虑 t 是两条路径上重复的点，因此对异或和没有贡献，需要异或一次将其贡献去掉。

于是问题就变成了 s_x \bigoplus s_y \bigoplus w_a \bigoplus w_t = k 是否成立。注意到 x, y, a, k 都是定值，根据消去律，w_t = k \bigoplus s_x \bigoplus s_y \bigoplus w_a。于是问题转化成了：在 x 到 y 的链上是否存在一个 t，使得 t 的权值是 W= k \bigoplus s_x \bigoplus s_y \bigoplus w_a。也即查询这条链上权值为 W 的点的个数。这是一个经典的树上差分问题：我们只需要查询 (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，用一个全局桶维护当前节点到根的权值数量即可，详见代码。

时间复杂度为 O(n \log n) 或 O(n \alpha (n))。其中 \log n 或 \alpha (n) 是求 LCA 的开销。因为本身就需要离线询问，std 使用的是 tarjan 求 LCA 的 O(n \alpha (n)) 的做法，使用倍增求 LCA 可能需要一定的常数优化，但是根据验题人程序，也可以通过本题。

(C++)

#include <array>
#include <vector>
#include <iostream>

const int maxn = 1000005;
const int maxw = 10000007;

int n, q;
std::array<std::vector<int>, maxn> e;
std::array<int, maxn> a, b, lca, ufs, rnk, anc, kk, cnt, fa, k, ans;
std::array<bool, maxn> vis;
std::array<std::vector<std::pair<int, int> >, maxn> qry, QQ;
std::array<std::pair<int, int>, maxn> Q;
std::array<int, maxw> bk;

void dfs2(const int u);
void dfs(const int u, const int f);

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    rnk[ufs[i] = anc[i] = i] = 1;
  }
  for (int u, v, i = 1; i < n; ++i) {
    std::cin >> u >> v;
    e[u].push_back(v); e[v].push_back(u);
  }
  for (int i = 1, u, v; i <= q; ++i) {
    std::cin >> u >> v >> kk[i];
    qry[u].push_back(std::make_pair(v, i));
    qry[v].push_back(std::make_pair(u, i));
    Q[i] = std::make_pair(u, v);
  }
  dfs(1, 0);
  for (int i = 1; i <= q; ++i) if ((k[i] = b[Q[i].first] ^ b[Q[i].second] ^ a[lca[i]] ^ kk[i]) < maxw) {
    QQ[Q[i].first].push_back(std::make_pair(i, 1));
    QQ[Q[i].second].push_back(std::make_pair(i, 1));
    QQ[lca[i]].push_back(std::make_pair(i, -1));
    QQ[fa[lca[i]]].push_back(std::make_pair(i, -1));
  }
  dfs2(1);
  std::array<std::string, 2> prt{"nO\n", "yEs\n"};
  for (int i = 1; i <= q; ++i) std::cout << prt[ans[i] > 0];
}

int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }

void dfs(const int u, const int f) {
  b[u] = a[u] ^ b[f];
  fa[u] = f;
  for (auto v : e[u]) if (v != f) {
    dfs(v, u);
    int x = find(u), y = find(v);
    if (rnk[x] > rnk[y]) std::swap(x, y);
    anc[ufs[x] = y] = u;
    if (rnk[x] == rnk[y]) ++rnk[y];
  }
  for (auto [v, i] : qry[u]) if (vis[v]) {
    lca[i] = anc[find(v)];
  }
   vis[u] = true;
}

void dfs2(const int u) {    // 这里是树上差分对应求结果的 dfs 函数
  ++bk[a[u]];
  for (auto [i, w] : QQ[u]) {
    ans[i] += w * bk[k[i]];
  }
  for (auto v : e[u]) if (v != fa[u]) {
    dfs2(v);
  }
  --bk[a[u]];
}