1000ms

Difficulty: 10

所属公司 : 美团

时间 :2025年9月6日-开发岗

算法与标签>线段树

会员专享

请先登录，开通会员或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路题解

关键观察

点 $u$ 的权值 $w_u$ 只依赖 $a_u$ 以及 $u$ 的直接子节点的取值集合 ${a_v\mid v\in \mathrm{child}(u)}$ 。因而一次把 $a_x$ 改成 $y$ 的修改，至多影响 两个点： $x$ 自身（若 $x$ 有子）与其父亲 $p=\mathrm{fa}(x)$ （因为 $w_p$ 里包含 $a_p\oplus a_x$ 这一候选）。这不会继续向更高祖先传递（ $w_{\mathrm{fa}(mathrm{fa}(x))}$ 不依赖 $w_p$ ）。
区间查询（类型 $2$ ）是“按编号”的最大值；子树查询（类型 $3$ ）可以用欧拉序把子树压成一段区间。因此维护两棵最大值线段树即可：

题目内容

小美有一棵 $n$ 个节点(编号为 $1$ ~ $n$ )、由 $n-1$ 条边构成的无向树，根节点为 $1$ 。每个节点 $i$ 有一个值 $a_i$ 。对于任意节点 $u$ ，其权值定义如下：

如果 $u$ 有子节点，则权值为该节点与所有子节点值的按位异或的最大值，即

如果 $u$ 是叶子节点，则权值为 $a_u$ 。