思路
为了求出恰好进行一次操作后，整棵树美丽值（即从根到所有节点路径权值和的最大值）的最小可能值，我们可以枚举树上的每一个节点 u（从 1 到 n），假设我们将以 u 为根的子树内的所有节点点权异或上 x。
我们定义两个状态数组来记录路径前缀和：
bef[u]：从根节点到u节点的简单路径上，原点权之和。aft[u]：从根节点到u节点的简单路径上，异或后的点权（即）之和。
当我们枚举选定操作节点 u 时，整棵树的节点可以被划分为两部分：不在 u 子树中的点 和 在 u 子树中的点。操作后的树的美丽值就是这两部分的最大值。
分析
1. 不在 u 子树中的点
这些点不受异或操作的影响，它们的路径和维持原样。
利用 DFS 序（dfn），我们可以把树上结构拍扁成一维数组。假设 u 子树对应的区间为 [l, r)，那么不在子树内的点就对应着区间 [0, l) 和 [r, n)。
计算方法：直接使用线段树，在这两个区间内查询 bef 数组的最大值即可。
2. 在 u 子树中的点
考虑 u 子树内的任意节点 v，在对其祖先 u 及其子树应用异或操作后，它的新路径和由两部分组成：
- 未被操作的部分：从根节点到
u的父亲节点fa[u]。这部分的路径和维持原样，即bef[fa[u]]。 - 被操作的部分：从
u到v的路径。这部分全部被异或了x，其路径和可以通过差分获得，即aft[v] - aft[fa[u]]。
因此，节点 v 的新路径和贡献可以表示为：
稍微变换一下形式：
计算方法：
因为我们已经选定了 u 节点，所以前半部分的偏移量 add = bef[fa[u]] - aft[fa[u]] 是一个常数。
要求这一部分的最大值，我们只需要求出子树内所有的 aft[v] 的最大值，然后再统一加上 add。这同样可以通过在 AFT 线段树中查询区间 [l, r) 的最大值来实现。
统计答案
对于每一个枚举的 u，我们取上述两部分的最大值，这就是选择操作 u 时整棵树的美丽值。
最后，将所有 u 对应的美丽值取最小值，即为最终答案。
参考代码 (C++)
#include "bits/stdc++.h"
__attribute__((constructor)) void Feijoa_Li() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
************************************
░▒▓████████▓▒ ░▒▓████████▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓██████▓▒░ ░▒▓██████▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓██████▓▒░ ░▒▓██████▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒ ░▒▓████████▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓█▓▒░ ░▒▓█▓▒░ ░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒░ ▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░░▒▓█▓▒ ░▒▓█▓▒░ ░▒▓█▓▒░
░▒▓█▓▒░ ░▒▓████████▓▒ ░▒▓█▓▒░ ░▒▓██████▓▒░ ░▒▓██████▓▒░ ░▒▓█▓▒░░▒▓█▓▒ ░▒▓████████▓▒ ░▒▓█▓▒░
*/
using u128 = unsigned __int128;
using i128 = __int128;
using u64 = unsigned long long;
using i64 = long long;
using u32 = unsigned int;
using i32 = int;
#define dbg std::cout << "line : " << __LINE__ << " "
#define int long long
constexpr i64 inf = 1e18L;
constexpr i64 MOD = 1e9 + 7;
/*------------------------------------------------------------------------------------------------------*/
template <class I, class T>
struct Seg {
std::vector<T> t;
std::vector<I> i;
void ap(int p, const T& v) {
i[p].ap(v);
t[p].ap(v);
}
void pu(int p) { i[p] = i[p << 1] + i[p << 1 | 1]; }
void pd(int p) {
ap(p << 1, t[p]);
ap(p << 1 | 1, t[p]);
t[p] = T();
}
void st(int p, int l, int r, int x, const I& v) {
if (r - l == 1) {
i[p] = v;
return;
}
int m = l + r >> 1;
pd(p);
if (x < m) {
st(p << 1, l, m, x, v);
} else {
st(p << 1 | 1, m, r, x, v);
}
pu(p);
}
I rq(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) return I();
if (l >= x && r <= y) return i[p];
int m = l + r >> 1;
pd(p);
return rq(p << 1, l, m, x, y) + rq(p << 1 | 1, m, r, x, y);
}
void ra(int p, int l, int r, int x, int y, const T& v) {
if (l >= y || r <= x) return;
if (l >= x && r <= y) return ap(p, v);
int m = l + r >> 1;
pd(p);
ra(p << 1, l, m, x, y, v);
ra(p << 1 | 1, m, r, x, y, v);
pu(p);
}
template <class F>
int ff(int p, int l, int r, int x, int y, F&& f) {
if (l >= y || r <= x) return -1;
if (l >= x && r <= y) {
if (!f(i[p], l, r)) return -1;
if (r - l == 1) return l;
}
int m = l + r >> 1;
pd(p);
int res = ff(p << 1, l, m, x, y, f);
if (res == -1) {
res = ff(p << 1 | 1, m, r, x, y, f);
}
return res;
}
template <class F>
int fl(int p, int l, int r, int x, int y, F&& f) {
if (l >= y || r <= x) return -1;
if (l >= x && r <= y) {
if (!f(i[p], l, r)) return -1;
if (r - l == 1) return l;
}
int m = l + r >> 1;
pd(p);
int res = fl(p << 1 | 1, m, r, x, y, f);
if (res == -1) {
res = fl(p << 1, l, m, x, y, f);
}
return res;
}
};
struct T {
void ap(const T& t) {}
};
struct I {
bool ok = false;
int max = -inf;
void ap(const T& t) {}
};
I operator+(const I& a, const I& b) {
if (!a.ok && !b.ok) return I();
if (!a.ok) return b;
if (!b.ok) return a;
I res = {1, std::max(a.max, b.max)};
return res;
}
/*
*/
void slu() {
int n, x;
std::cin >> n >> x;
std::vector<int> w(n + 1, 0);
for (int i = 1; i <= n; i++) std::cin >> w[i];
std::vector<std::vector<int>> adj(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<int> dfn(n + 1, 0), sz(n + 1, 0), fa(n + 1, 0);
std::vector<int> aft(n + 1, 0), bef(n + 1, 0);
int p = 0;
auto dfs = [&](auto&& self, int u, int f) -> void {
dfn[u] = p++;
sz[u]++;
fa[u] = f;
bef[u] = bef[f] + w[u];
aft[u] = aft[f] + (w[u] ^ x);
for (auto v : adj[u]) {
if (v == f) continue;
self(self, v, u);
sz[u] += sz[v];
}
};
dfs(dfs, 1, 0);
Seg<I, T> AFT, BEF;
AFT.i.assign(n << 2, I());
AFT.t.assign(n << 2, T());
BEF.i.assign(n << 2, I());
BEF.t.assign(n << 2, T());
for (int i = 1; i <= n; i++) {
int id = dfn[i];
AFT.st(1, 0, n, id, {1, aft[i]});
BEF.st(1, 0, n, id, {1, bef[i]});
}
int res = inf;
for (int i = 1; i <= n; i++) {
int l = dfn[i];
int r = l + sz[i];
int add = bef[fa[i]] - aft[fa[i]];
int tmp = inf;
auto bef_l = BEF.rq(1, 0, n, 0, l);
auto bef_r = BEF.rq(1, 0, n, r, n);
tmp = std::max(bef_l.max, bef_r.max);
auto aft_ = AFT.rq(1, 0, n, l, r);
tmp = std::max(tmp, aft_.max + add);
res = std::min(res, tmp);
}
std::cout << res << '\n';
return;
}
i32 main() {
int t = 1;
std::cin >> t;
while (t--) slu();
return 0;
}
京公网安备 11010502036488号