与非

GitHub跳转原题关系图返回列表

nand 逐位独立,一段点序列诱导的函数只需 F(0^k) 与 F(1^k) 两个掩码即可刻画;函数复合满足结合律,于是用线段树维护正反两个方向的复合,树链剖分把路径拆成 O(log n) 段按序拼接。

OJ: roj

题目 ID: 1762

难度:提高+/省选-

标签:树链剖分线段树位运算python

创建: 2026-10-08 08:51

更新: 2026-10-08 08:51

形式化题目

定义 kk 位按位与非运算

x nand y=¬(x&y)&(2k−1),x\ \mathrm{nand}\ y = \lnot(x \mathbin{\&} y) \mathbin{\&} (2^k - 1),

即先按位与、再按位取反,最后只保留低 kk 位。

给定一棵 nn 个结点的树,第 ii 个结点带权值 wiw_i(0≤wi<2k0 \le w_i < 2^k)。依次处理 mm 个操作:

  • Replace x y:wx←yw_x \leftarrow y;
  • Query x y:设 x→yx \to y 的路径依次为 S1,S2,…,SLS_1, S_2, \dots, S_L(S1=xS_1 = x,SL=yS_L = y,L≥1L \ge 1),定义
f(0)=0,f(i)=f(i−1) nand wSi(1≤i≤L),f(0) = 0, \qquad f(i) = f(i-1)\ \mathrm{nand}\ w_{S_i} \quad (1 \le i \le L),

输出 f(L)f(L)。

数据范围:1≤n,m≤1051 \le n, m \le 10^5,1≤k≤321 \le k \le 32,0≤wi,y<2k0 \le w_i, y < 2^k。时间限制 2000 ms,空间限制 256 MB。

以题面样例(n=3n = 3、k=3k = 3、链 1−2−31-2-3、w=(2,7,3)w = (2, 7, 3))对照:Query 2 3 沿 2→32 \to 3 得 f(1)=0 nand 7=7f(1) = 0\ \mathrm{nand}\ 7 = 7、f(2)=7 nand 3=¬3&7=4f(2) = 7\ \mathrm{nand}\ 3 = \lnot 3 \& 7 = 4; 随后 Replace 1 3,Query 1 1 是长度为 1 的退化路径,得 0 nand 3=70\ \mathrm{nand}\ 3 = 7。 注意反向走 3→23 \to 2 会得到 00,可见路径方向是 x→yx \to y 且结果对方向敏感。

正解

思路

朴素做法的瓶颈。 每次查询沿路径逐点折叠,单次 O(n)O(n),总计 O(nm)O(nm),n,m≤105n, m \le 10^5 时是 101010^{10} 量级,必然超时。直觉上树上路径求值应该上「树链剖分 + 线段树」,但 nand\mathrm{nand} 不满足结合律:

(1 nand 1) nand 0=0 nand 0=1,1 nand (1 nand 0)=1 nand 1=0(k=1),(1\ \mathrm{nand}\ 1)\ \mathrm{nand}\ 0 = 0\ \mathrm{nand}\ 0 = 1, \qquad 1\ \mathrm{nand}\ (1\ \mathrm{nand}\ 0) = 1\ \mathrm{nand}\ 1 = 0 \quad (k = 1),

两边的括号位置给出不同答案。所以不能像区间和、区间异或那样把左右子区间的「答案」直接串起来,线段树这条路看似被堵死。

(顺带澄清一个常见口误:nand\mathrm{nand} 本身是交换的——¬(x&y)=¬(y&x)\lnot(x \& y) = \lnot(y \& x);真正让本题棘手的只是「折叠一段序列」这件事不可结合。)

关键观察:值不可结合,函数可以。 换一个视角:不要维护「这一段折叠出来等于多少」,而是维护「这一段把输入变成什么」——即这一段序列诱导的变换 FF。虽然 nand\mathrm{nand} 不可结合,但函数复合天然满足结合律:

FC∘(FB∘FA)=(FC∘FB)∘FA,F_C \circ (F_B \circ F_A) = (F_C \circ F_B) \circ F_A,

于是线段树可以照常合并——只不过合并的是变换而不是数值。

把变换压成两个掩码。 还剩一个问题:kk 位输入的变换有 22k2^{2^k} 种,无法存储。但按位运算逐位独立:第 ii 位的输出只依赖第 ii 位的输入,没有进位、借位,位与位之间互不影响。因此每一位上的变换都只是 {0,1}→{0,1}\{0,1\} \to \{0,1\} 的映射,一共只有 4 种,而它由「输入 0 时的输出」与「输入 1 时的输出」唯一确定。

把 kk 位放在一起,一段区间诱导的变换 FF 就只需两个 kk 位整数刻画:

A=F(0k),B=F(1k),F(x)=((x&B)∣(¬x&A))&mask,mask=2k−1.A = F(0^k), \qquad B = F(1^k), \qquad F(x) = \bigl((x \mathbin{\&} B) \mid (\lnot x \mathbin{\&} A)\bigr) \mathbin{\&} mask, \qquad mask = 2^k - 1.

逐位看这个式子就是:输入为 1 的位取 BB 的对应位、输入为 0 的位取 AA 的对应位。于是 22k2^{2^k} 种变换被无损压缩进两个整数。

单点与复合。

变换 A=F(0k)A = F(0^k) B=F(1k)B = F(1^k)
恒等 F(x)=xF(x) = x 00 maskmask
单点 Fw(x)=¬(x&w)&maskF_w(x) = \lnot(x \& w) \& mask maskmask (¬w)&mask(\lnot w) \& mask
复合 Fafter∘FbeforeF_{after} \circ F_{before} (Abef&Baft)∣(¬Abef&Aaft)(A_{bef} \& B_{aft}) \mid (\lnot A_{bef} \& A_{aft}) (Bbef&Baft)∣(¬Bbef&Aaft)(B_{bef} \& B_{aft}) \mid (\lnot B_{bef} \& A_{aft})

复合公式的含义很直白:先做 beforebefore 后,输入 00 变成了 AbefA_{bef};它的第 ii 位为 1 的位在 afterafter 里走 BaftB_{aft}、为 0 的位走 AaftA_{aft},按位或起来即得新变换在 00 处的取值。

线段树 + 树链剖分。 线段树的每个结点维护两套掩码:正向(按 dfs 序递增,即自顶向下)的 (A,B)(A, B) 与反向(按 dfs 序递减,即自底向上)的 (A,B)(A, B);单点修改 O(log⁡n)O(\log n),区间查询直接返回变换。

树链剖分把路径 x→yx \to y 拆成 O(log⁡n)O(\log n) 条重链上的连续区间,拼接时必须严格区分两个方向:

  • xx 侧(xx 向上到 LCA\mathrm{LCA},含 LCA\mathrm{LCA}):沿链向上跳,先处理的是较深的一段,而它在路径上排在前面——是内层函数,用反向查询,并按「新段在外层」累积:F←Fnew∘FF \leftarrow F_{new} \circ F;
  • yy 侧(LCA\mathrm{LCA} 的孩子向下到 yy,不含 LCA\mathrm{LCA}):同样沿链向上跳,先处理的是较深的一段,但它在路径上排在后面——是外层函数,用正向查询,并按「新段在内层」累积:F←F∘FnewF \leftarrow F \circ F_{new};
  • LCA\mathrm{LCA} 归 xx 侧,只算一次,别重复计入;
  • 最后把两侧按「xx 侧先、yy 侧后」合起来:F=Fy∘FxF = F_y \circ F_x,答案即 A=F(0k)A = F(0^k)(初始值为 00)。

两个易错点。

  1. k=32k = 32 时 1u << k 是未定义行为,必须特判 mask=0xFFFFFFFFmask = \texttt{0xFFFFFFFF}(C++ 用 unsigned int;Python 的整数无溢出之虞,(1 << k) - 1 直接可用)。
  2. ¬\lnot 作用于整个机器字,每次取反后必须立刻 & mask,否则高位会污染结果。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 23:10
# update_at: 2026-10-08 08:51
#
# 一本通 1762《与非》:树链剖分 + 线段树维护「逐位变换」的复合。
# nand 逐位独立,一段点序列诱导的函数 F 完全由 F(0^k) 与 F(1^k) 两个掩码决定,
# 而「函数复合」满足结合律——于是不可结合的 nand 序列被搬进可结合的复合世界。
# 线段树每个结点同时存正向(dfs 序递增)与反向(dfs 序递减)两份复合结果,
# 树链剖分把树上路径拆成 O(log n) 段按顺序拼接,整体 O(n + m log^2 n)。

import sys

THRESH = 32  # 区间长度不超过它就直接逐点扫,省掉线段树查询的固定开销

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = tuple[list[int], list[int]]  # CSR 邻接表:(start, nb),start[u]..start[u+1] 是 u 的邻居区间
type Hld = tuple[list[int], list[int], list[int], list[int], list[int]]
# Hld = (par, dep, top, dfn, wd):父结点 / 深度 / 重链链头 / 剖分下标 / 按下标存放的点权
type Seg = tuple[list[int], list[int], list[int], list[int], int]
# Seg = (fa, fb, ba, bb, size):正向 F(0)、正向 F(1)、反向 F(0)、反向 F(1) 四张掩码表 + 叶子偏移


def build_adj(n: int, eu: list[int], ev: list[int]) -> Adj:
    """把 n-1 条无向边按计数排序压成 CSR:邻居连续存放,常数小于 list of list。"""
    deg = [0] * (n + 2)
    for e in range(1, n):
        deg[eu[e]] += 1
        deg[ev[e]] += 1
    start = [0] * (n + 2)
    acc = 0
    for u in range(1, n + 1):
        start[u] = acc
        acc += deg[u]
    start[n + 1] = acc
    fill = start[:]
    nb = [0] * (2 * (n - 1))
    for e in range(1, n):
        a, b = eu[e], ev[e]
        nb[fill[a]] = b
        fill[a] += 1
        nb[fill[b]] = a
        fill[b] += 1
    return start, nb


def heavy_light(n: int, w: list[int], adj: Adj) -> Hld:
    """树链剖分(两遍迭代,n=1e5 且可能是纯链,递归会爆栈)。

    第一遍 BFS 定父子与深度,逆 BFS 序回推子树大小与重儿子;
    第二遍沿重链铺剖分下标,轻儿子各开一条新链,同一条链的下标随深度递增。
    """
    start, nb = adj
    par = [0] * (n + 1)
    dep = [0] * (n + 1)
    order = [1]
    for u in order:  # 边遍历边扩容,迭代顺序即 BFS 序
        du = dep[u] + 1
        pu = par[u]
        for j in range(start[u], start[u + 1]):
            v = nb[j]
            if v != pu:
                par[v] = u
                dep[v] = du
                order.append(v)

    siz = [1] * (n + 1)
    siz[0] = 0  # 哨兵:没有重儿子时比大小用
    heavy = [0] * (n + 1)
    for i in range(n - 1, 0, -1):  # 跳过 order[0]=根,其余按逆 BFS 序保证儿子先算完
        u = order[i]
        p = par[u]
        siz[p] += siz[u]
        if siz[u] > siz[heavy[p]]:
            heavy[p] = u

    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    wd = [0] * n
    cur = 0
    stk = [1]
    stkt = [1]
    while stk:
        u = stk.pop()
        t = stkt.pop()
        while u:
            top[u] = t
            dfn[u] = cur
            wd[cur] = w[u]
            cur += 1
            hv = heavy[u]
            pu = par[u]
            for j in range(start[u], start[u + 1]):
                v = nb[j]
                if v != pu and v != hv:  # 轻儿子各自开一条新链
                    stk.append(v)
                    stkt.append(v)
            u = hv
    return par, dep, top, dfn, wd


def build_seg(wd: list[int], mask: int) -> Seg:
    """按剖分下标建迭代式线段树,每结点存正反两个方向的变换 (F(0^k), F(1^k))。

    单点的 F(x) = ~(x & w) 只取低 k 位,故 F(0) = mask、F(1) = mask ^ w;
    补到 2 的幂的空叶子用恒等变换(F(0) = 0、F(1) = mask),不会干扰区间查询。
    """
    n = len(wd)
    size = 1
    while size < n:
        size <<= 1
    fa = [0] * (2 * size)  # 正向 F(0):dfs 序递增方向
    fb = [0] * (2 * size)  # 正向 F(1)
    ba = [0] * (2 * size)  # 反向 F(0):dfs 序递减方向
    bb = [0] * (2 * size)  # 反向 F(1)
    for i in range(size):
        p = size + i
        if i < n:
            fa[p] = ba[p] = mask
            fb[p] = bb[p] = mask ^ wd[i]
        else:
            fa[p] = ba[p] = 0
            fb[p] = bb[p] = mask
    for p in range(size - 1, 0, -1):
        l = p << 1
        r = l | 1
        la = fa[l]
        lb = fb[l]
        ra = fa[r]
        rb = fb[r]
        fa[p] = (la & rb) | (~la & ra)  # 先左后右:F(x) = R(L(x))
        fb[p] = (lb & rb) | (~lb & ra)
        la = ba[l]
        lb = bb[l]
        ra = ba[r]
        rb = bb[r]
        ba[p] = (ra & lb) | (~ra & la)  # 先右后左:G(x) = L(R(x))
        bb[p] = (rb & lb) | (~rb & la)
    return fa, fb, ba, bb, size


def apply_fwd(val: int, lo: int, hi: int, wd: list[int], mask: int, seg: Seg) -> int:
    """把剖分下标区间 [lo, hi] 上的点按下标递增顺序(自顶向下)依次 nand 到 val 上。"""
    if hi - lo <= THRESH:  # 短区间直接扫,比走线段树快
        for i in range(lo, hi + 1):
            val = mask ^ (val & wd[i])
        return val
    fa, fb, _ba, _bb, size = seg
    l = lo + size
    r = hi + size + 1
    pend = []
    while l < r:
        if l & 1:
            val = (~val & fa[l]) | (val & fb[l])
            l += 1
        if r & 1:
            r -= 1
            pend.append(r)  # 右半边结点覆盖的下标更小,留到循环后按序施加
        l >>= 1
        r >>= 1
    for p in reversed(pend):
        val = (~val & fa[p]) | (val & fb[p])
    return val


def apply_bwd(val: int, lo: int, hi: int, wd: list[int], mask: int, seg: Seg) -> int:
    """把剖分下标区间 [lo, hi] 上的点按下标递减顺序(自底向上)依次 nand 到 val 上。"""
    if hi - lo <= THRESH:
        for i in range(hi, lo - 1, -1):
            val = mask ^ (val & wd[i])
        return val
    _fa, _fb, ba, bb, size = seg
    l = lo + size
    r = hi + size + 1
    pend = []
    while l < r:
        if l & 1:
            pend.append(l)  # 左半边结点覆盖的下标更大,留到最后按逆序施加
            l += 1
        if r & 1:
            r -= 1
            val = (~val & ba[r]) | (val & bb[r])
        l >>= 1
        r >>= 1
    for p in reversed(pend):
        val = (~val & ba[p]) | (val & bb[p])
    return val


def path_value(x: int, y: int, mask: int, hld: Hld, seg: Seg) -> int:
    """求 x -> y 路径的折叠结果 f(L):初始值 0,沿路径逐点 nand。

    路径被 LCA 切成两半:x 侧沿链向上跳,段内下标递减,用反向查询;y 侧自顶向下,
    段内下标递增,用正向查询。x 侧在路径上排在前面,故先施加;y 侧各段是自底向上
    收集到的,要逆序(变成自顶向下)才与路径同向。
    """
    par, dep, top, dfn, wd = hld
    val = 0  # f 的初始值
    pend = []  # lca -> y 一侧的区间,自底向上收集,最后逆序施加
    while top[x] != top[y]:
        if dep[top[x]] >= dep[top[y]]:
            val = apply_bwd(val, dfn[top[x]], dfn[x], wd, mask, seg)
            x = par[top[x]]
        else:
            pend.append((dfn[top[y]], dfn[y]))
            y = par[top[y]]
    if dep[x] >= dep[y]:  # y 就是 lca,整段归 x 侧,lca 不重复计入
        val = apply_bwd(val, dfn[y], dfn[x], wd, mask, seg)
    else:  # x 就是 lca,y 侧还要接上 lca 以下的点
        val = apply_bwd(val, dfn[x], dfn[x], wd, mask, seg)
        pend.append((dfn[x] + 1, dfn[y]))
    for lo, hi in reversed(pend):
        val = apply_fwd(val, lo, hi, wd, mask, seg)
    return val


def set_value(x: int, w: int, mask: int, hld: Hld, seg: Seg) -> None:
    """把结点 x 的点权改成 w,再自底向上重算线段树沿途的结点。"""
    _par, _dep, _top, dfn, wd = hld
    fa, fb, ba, bb, size = seg
    d = dfn[x]
    wd[d] = w
    p = size + d
    fa[p] = ba[p] = mask
    fb[p] = bb[p] = mask ^ w
    p >>= 1
    while p:
        l = p << 1
        r = l | 1
        la = fa[l]
        lb = fb[l]
        ra = fa[r]
        rb = fb[r]
        fa[p] = (la & rb) | (~la & ra)  # 先左后右:F(x) = R(L(x))
        fb[p] = (lb & rb) | (~lb & ra)
        la = ba[l]
        lb = bb[l]
        ra = ba[r]
        rb = bb[r]
        ba[p] = (ra & lb) | (~ra & la)  # 先右后左:G(x) = L(R(x))
        bb[p] = (rb & lb) | (~rb & la)
        p >>= 1


def solve() -> None:
    """读入树与操作序列,逐条处理并输出每个 Query 的答案。"""
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))
    mask = (1 << k) - 1  # k 可达 32,Python 整数无溢出之虞
    w = [0] * (n + 1)
    for i in range(1, n + 1):
        w[i] = int(next(it))
    eu = [0] * n
    ev = [0] * n
    for e in range(1, n):
        eu[e] = int(next(it))
        ev[e] = int(next(it))

    hld = heavy_light(n, w, build_adj(n, eu, ev))
    seg = build_seg(hld[4], mask)

    out = []
    for _ in range(m):
        op = next(it)
        x = int(next(it))
        if op == b"Query":
            out.append(path_value(x, int(next(it)), mask, hld, seg))
        else:
            set_value(x, int(next(it)) & mask, mask, hld, seg)
    sys.stdout.write("\n".join(map(str, out)) + ("\n" if out else ""))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 22:45
 * update_at: 2026-10-07 22:45
 */
// 一本通 1762《与非》
//
// 题意:k 位 nand 运算 x nand y = ~(x & y)(结果只取低 k 位)。给一棵树,点权 w[i],
//       Query x y:设 x 到 y 的路径依次是 S1..SL,f(0)=0,f(i) = f(i-1) nand w[Si],
//       输出 f(L)。Replace x y:把 w[x] 改成 y。
//
// 做法:nand 逐位独立,一段序列诱导的函数 F 只需要 (F(0^k), F(1^k)) 两个掩码就能刻画,
//       而「函数复合」满足结合律,于是不可结合的 nand 序列被搬进可结合的复合世界:
//       线段树每个结点维护正/反两个方向的复合结果,树链剖分把路径拆成 O(log n) 段拼接。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned int u32;

const int MAXN = 100005;  // 结点数上限
const int MAXE = 200005;  // 无向边按两个方向各存一条,上限 2(n-1)

int n, m, k;
u32 MASK;       // 低 k 位全 1 的掩码
u32 wv[MAXN];  // 每个结点的点权(只保留低 k 位)

/* ---------- 链式前向星 ---------- */
int headArr[MAXN], eTo[MAXE], eNxt[MAXE], ecnt;

// 加一条 u -> v 的有向边。
void add_edge(int u, int v) {
    ecnt++;
    eTo[ecnt] = v;
    eNxt[ecnt] = headArr[u];
    headArr[u] = ecnt;
}

/* ---------- 树链剖分 ---------- */
int fa[MAXN], dep[MAXN], siz[MAXN], heavy_son[MAXN];  // 父亲 / 深度 / 子树大小 / 重儿子
int chain_top[MAXN], dfn[MAXN], node_of_dfn[MAXN];     // 链顶 / dfs 序 / 序对应的结点
int bfs_order[MAXN];                                   // 自根向下的 BFS 序,用来迭代剖分

// 求 x、y 的最近公共祖先(沿重链向上跳)。
int lca(int x, int y) {
    while (chain_top[x] != chain_top[y]) {
        if (dep[chain_top[x]] >= dep[chain_top[y]]) x = fa[chain_top[x]];
        else y = fa[chain_top[y]];
    }
    return dep[x] < dep[y] ? x : y;
}

/* ---------- 区间变换 ---------- */
// 一段连续区间诱导的函数 F。因为 nand 逐位独立,F 的第 i 位只依赖 x 的第 i 位,
// 所以 F 由两个值唯一确定:a = F(0^k)、b = F(1^k),且 F(x) = (x & b) | (~x & a)。
struct Trans {
    u32 a;  // F(0^k)
    u32 b;  // F(1^k)
};

Trans seg_fwd[MAXN << 2];  // 正向:按 dfn 递增(自顶向下)的顺序复合
Trans seg_bwd[MAXN << 2];  // 反向:按 dfn 递减(自底向上)的顺序复合

// 先做 before、后做 after 的复合结果,即 after ∘ before。
Trans merge_trans(Trans after, Trans before) {
    Trans res;
    res.a = ((before.a & after.b) | (~before.a & after.a)) & MASK;
    res.b = ((before.b & after.b) | (~before.b & after.a)) & MASK;
    return res;
}

// 单点权值 w 诱导的函数:F(x) = ~(x & w)(截断到低 k 位)。
Trans leaf_trans(u32 w) {
    Trans res;
    res.a = MASK;         // F(0) = ~(0 & w) = 全 1
    res.b = (~w) & MASK;  // F(1) = ~(1 & w) = ~w
    return res;
}

// 恒等函数 F(x) = x。
Trans ident_trans() {
    Trans res;
    res.a = 0;
    res.b = MASK;
    return res;
}

void build(int idx, int l, int r) {
    if (l == r) {
        seg_fwd[idx] = leaf_trans(wv[node_of_dfn[l]]);
        seg_bwd[idx] = seg_fwd[idx];
        return;
    }
    int mid = (l + r) >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    seg_fwd[idx] = merge_trans(seg_fwd[idx << 1 | 1], seg_fwd[idx << 1]);
    seg_bwd[idx] = merge_trans(seg_bwd[idx << 1], seg_bwd[idx << 1 | 1]);
}

// 单点修改:把 dfn 位置 pos 的点权换成 w。
void update(int idx, int l, int r, int pos, u32 w) {
    if (l == r) {
        seg_fwd[idx] = leaf_trans(w);
        seg_bwd[idx] = seg_fwd[idx];
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(idx << 1, l, mid, pos, w);
    else update(idx << 1 | 1, mid + 1, r, pos, w);
    seg_fwd[idx] = merge_trans(seg_fwd[idx << 1 | 1], seg_fwd[idx << 1]);
    seg_bwd[idx] = merge_trans(seg_bwd[idx << 1], seg_bwd[idx << 1 | 1]);
}

// 正向查询 [ql, qr]:结果按 dfn 递增顺序复合(先 dfn 小的、后 dfn 大的)。
Trans query_fwd(int idx, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return seg_fwd[idx];
    int mid = (l + r) >> 1;
    if (qr <= mid) return query_fwd(idx << 1, l, mid, ql, qr);
    if (ql > mid) return query_fwd(idx << 1 | 1, mid + 1, r, ql, qr);
    Trans left_part = query_fwd(idx << 1, l, mid, ql, qr);
    Trans right_part = query_fwd(idx << 1 | 1, mid + 1, r, ql, qr);
    return merge_trans(right_part, left_part);
}

// 反向查询 [ql, qr]:结果按 dfn 递减顺序复合(先 dfn 大的、后 dfn 小的)。
Trans query_bwd(int idx, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return seg_bwd[idx];
    int mid = (l + r) >> 1;
    if (qr <= mid) return query_bwd(idx << 1, l, mid, ql, qr);
    if (ql > mid) return query_bwd(idx << 1 | 1, mid + 1, r, ql, qr);
    Trans left_part = query_bwd(idx << 1, l, mid, ql, qr);
    Trans right_part = query_bwd(idx << 1 | 1, mid + 1, r, ql, qr);
    return merge_trans(left_part, right_part);
}

/* ---------- 路径查询 ---------- */
// 路径 x -> y 上依次施加各点权诱导的函数,返回总复合结果。
// 拆成两半:x 侧(x 向上到 lca,路径上先走的部分)与 y 侧(lca 的孩子向下到 y,后走的部分)。
// 注意「先走的部分是内层函数、后走的部分是外层函数」,所以两半的拼接方向相反。
Trans query_path(int x, int y) {
    int l = lca(x, y);
    Trans fx = ident_trans();  // x 侧:自底向上(dfn 递减),新处理的链段在后、是外层
    Trans fy = ident_trans();  // y 侧:自顶向下(dfn 递增),新处理的链段在前、是内层

    while (chain_top[x] != chain_top[l]) {
        fx = merge_trans(query_bwd(1, 1, n, dfn[chain_top[x]], dfn[x]), fx);
        x = fa[chain_top[x]];
    }
    fx = merge_trans(query_bwd(1, 1, n, dfn[l], dfn[x]), fx);  // lca 属于 x 侧

    while (chain_top[y] != chain_top[l]) {
        fy = merge_trans(fy, query_fwd(1, 1, n, dfn[chain_top[y]], dfn[y]));
        y = fa[chain_top[y]];
    }
    if (y != l) fy = merge_trans(fy, query_fwd(1, 1, n, dfn[l] + 1, dfn[y]));

    return merge_trans(fy, fx);  // 先 x 侧、后 y 侧
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    MASK = (k >= 32) ? 0xFFFFFFFFu : ((1u << k) - 1u);

    for (int i = 1; i <= n; i++) cin >> wv[i];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
    }

    /* 迭代式树链剖分:n 可达 1e5 且数据含纯链,递归会爆栈 */
    int qt = 0;
    fa[1] = 0;
    dep[1] = 0;
    bfs_order[qt++] = 1;
    for (int qh = 0; qh < qt; qh++) {
        int u = bfs_order[qh];
        for (int e = headArr[u]; e; e = eNxt[e]) {
            int v = eTo[e];
            if (v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            bfs_order[qt++] = v;
        }
    }
    for (int i = n - 1; i >= 0; i--) {  // 逆 BFS 序保证儿子先于父亲算完
        int u = bfs_order[i];
        siz[u] = 1;
        heavy_son[u] = 0;
        for (int e = headArr[u]; e; e = eNxt[e]) {
            int v = eTo[e];
            if (v == fa[u]) continue;
            siz[u] += siz[v];
            if (heavy_son[u] == 0 || siz[v] > siz[heavy_son[u]]) heavy_son[u] = v;
        }
    }
    {
        int cur = 0;
        int stack_node[MAXN], stack_top[MAXN], sp = 0;
        stack_node[sp] = 1;
        stack_top[sp] = 1;
        sp++;
        while (sp > 0) {
            sp--;
            int u = stack_node[sp], t = stack_top[sp];
            for (int x = u; x != 0; x = heavy_son[x]) {  // 沿重链一路铺下去
                chain_top[x] = t;
                cur++;
                dfn[x] = cur;
                node_of_dfn[cur] = x;
                for (int e = headArr[x]; e; e = eNxt[e]) {
                    int v = eTo[e];
                    if (v != fa[x] && v != heavy_son[x]) {  // 轻儿子各自开一条新链
                        stack_node[sp] = v;
                        stack_top[sp] = v;
                        sp++;
                    }
                }
            }
        }
    }

    build(1, 1, n);

    char op[16];
    while (m--) {
        int x;
        cin >> op >> x;
        if (op[0] == 'Q') {  // Query x y:第二个参数是结点编号
            int y;
            cin >> y;
            cout << query_path(x, y).a << '\n';  // f(L) = 总函数在 0 处的取值
        } else {  // Replace x y:第二个参数是新的点权
            u32 y;
            cin >> y;
            wv[x] = y;
            update(1, 1, n, dfn[x], y);
        }
    }
    return 0;
}

复杂度

  • 时间:建树 O(n)O(n);单次 Replace O(log⁡n)O(\log n);单次 Query 树剖最多跳 O(log⁡n)O(\log n) 条重链、每条链上查询 O(log⁡n)O(\log n),故 O(log⁡2n)O(\log^2 n)。总计 O(n+mlog⁡2n)O\bigl(n + m \log^2 n\bigr)。
  • 空间:树剖与线段树各 O(n)O(n),线段树按 4n4n 开、每结点存 4 个 32 位整数,n=105n = 10^5 时约 6 MB。
  • 实测(本机 g++-16 -O2):顶格点 n=m=105n = m = 10^5 纯链 0.04 s、毛毛虫 0.05 s、完全二叉树 0.07 s,峰值内存约 12 MB,离 2000 ms / 256 MB 余量极大;Python 版同阶(短区间用阈值 THRESH = 32 直接逐点扫,避开线段树的固定开销),最大点约 0.9 s。

总结

本题是「运算不可结合时,改用变换的复合」这一技巧的模板题,两个关键动作:

  1. 换对象:把「区间折叠出的值」换成「区间诱导的变换」。nand\mathrm{nand} 不可结合,但函数复合恒满足结合律,线段树因此复活。
  2. 换表示:kk 位按位运算逐位独立,变换 FF 只需 F(0k)F(0^k) 与 F(1k)F(1^k) 两个掩码即可无损表示,22k2^{2^k} 种变换被压进两个整数;单点、复合、求值全部是常数次位运算。

剩下的就是树链剖分的常规拼接,但方向是本题真正的坑:路径是有序序列,xx 侧要用反向复合、yy 侧要用正向复合,两侧的累积方向还相反,LCA\mathrm{LCA} 只能算一次。凡是「线段树 + 树上路径 + 不可结合的运算」,这一套「双向维护 + 两侧反向拼接」几乎是标准套路。

关于素材与数据:本题素材目录带数据生成脚本 data.py,说明 data/ 是自造数据;题面 content.md 也有残留缺损(ff 的定义只剩 \0\ 残片),本解按题面样例反推为 f(0)=0f(0) = 0、f(i)=f(i−1) nand wSif(i) = f(i-1)\ \mathrm{nand}\ w_{S_i}(沿 x→yx \to y),这与网络流传的同题题解一致,样例 4 / 7 亦完全吻合。

需要如实指出的是:随仓 data/problem*.out 由素材源的 std.cpp 生成,而该 std.cpp 在 yy 侧跨多条重链拼接时把复合顺序写反了(先深后浅,即 fy = merge_trans(query_fwd(...), fy)),这与题面 x→yx \to y 的语义不符——同一棵树形状不同、路径与权值完全相同,它的输出都会变,例如路径 1−2−3−4−51-2-3-4-5、权值 0,1,0,3,30,1,0,3,3、k=2k = 2 时,链状树给 3、20 个结点的树给 0,可见它并非一个自洽的语义。本解按题面语义实现(先浅后深),因此第 1、2、3、8 组数据(单链 / 退化路径,yy 侧只有一段)与随仓 .out 完全一致,而第 4、5、6、7、9、10 组(yy 侧跨多链)不一致;这些点的正确答案已用独立的朴素暴力(BFS 求路径后逐点折叠)在 n≤5000n \le 5000 的全部测例上逐行核对通过。