仓库选址

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

M≤15 时异或只改距离的低 4 位,用换根 DP 同时维护距离和与距离 mod 16 的分布,O(16n) 求出每点到全树的花费之和。

OJ: roj

题目 ID: 1771

难度:提高

标签:动态规划换根DP位运算树python

创建: 2026-10-08 01:19

更新: 2026-10-08 01:19

形式化题目

给一棵 nn 个节点的无向树,边权为正整数,记 dis(a,b)dis(a,b) 为 a,ba,b 间唯一路径的长度。给定常数 MM,定义两点间花费为 dis(a,b)⊕Mdis(a,b) \oplus M(按位异或)。对每个 i∈[1,n]i \in [1,n] 求

Si=∑j=1n(dis(i,j)⊕M),S_i = \sum_{j=1}^{n} \big( dis(i,j) \oplus M \big),

其中 j=ij = i 的项为 00(题面要求的是「到其他所有星球」,自己不计入花费)。

数据规模:n⩽100000n \leqslant 100000,M⩽15M \leqslant 15,答案不超过 2×1092 \times 10^9。

正解

思路

先看暴力:对每个 ii 单独 DFS 求出所有 dis(i,j)dis(i,j),再逐个异或求和,复杂度 O(n2)O(n^2)。n=105n = 10^5 时是 101010^{10} 量级,必然超时。

瓶颈在于「每个点都要一遍全树」,而树上这类「对每个点求全树统计量」的问题有标准武器——换根 DP。但直接换根只能维护距离和 ∑jdis(i,j)\sum_j dis(i,j),本题求的是 ∑j(dis(i,j)⊕M)\sum_j (dis(i,j) \oplus M),异或不是线性运算,不能直接累加。

突破口是数据范围里的 M⩽15M \leqslant 15。15=(1111)215 = (1111)_2,MM 只占二进制低 4 位。把距离按 16 拆开:

dis=16k+r,0⩽r<16,  r=dis mod 16.dis = 16k + r, \qquad 0 \leqslant r < 16, \; r = dis \bmod 16 .

由于 16k16k 的低 4 位全为 00,而 MM 的高位全为 00,异或时两边互不干扰:

dis⊕M=16k+(r⊕M).dis \oplus M = 16k + (r \oplus M).

又因为 r<16r < 16、M<16M < 16,所以 r⊕M<16r \oplus M < 16,不会向第 4 位进位,于是可以放心地把异或还原成加减法:

dis⊕M=dis+((dis mod 16)⊕M)−(dis mod 16)⏟只与 dis mod 16 有关的修正量 Δ(dis mod 16).dis \oplus M = dis + \underbrace{\big((dis \bmod 16) \oplus M\big) - (dis \bmod 16)}_{\text{只与 } dis \bmod 16 \text{ 有关的修正量 } \Delta(dis \bmod 16)} .

这一步把「非线性的异或」换成了「距离本身 + 一个只依赖 dis mod 16dis \bmod 16 的修正量」。对 ii 求和:

Si=∑j≠idis(i,j)  +∑r=015Δ(r)⋅#{j≠i:dis(i,j) mod 16=r}.S_i = \sum_{j \ne i} dis(i,j) \; + \sum_{r=0}^{15} \Delta(r) \cdot \#\{ j \ne i : dis(i,j) \bmod 16 = r \}.

左边是标准的「全树距离和」,右边只需要「距离模 16 的分布」——只有 16 个桶。两个量都能换根 DP 维护,于是复杂度降到 O(16n)O(16n)。

具体做法分两趟 DFS(这里全部写成迭代,避免链状数据爆栈):

  1. 自底向上(子树 DP)。定根为 1。对每个 uu 维护 subusub_u(子树内到 uu 的距离和)、szusz_u(子树大小)、fu,rf_{u,r}(子树内到 uu 距离 ≡r(mod16)\equiv r \pmod{16} 的点数,含 uu 自身)。合并儿子 vv(边权 ww)时:szu+=szvsz_u \mathrel{+}= sz_v,subu+=subv+szv⋅wsub_u \mathrel{+}= sub_v + sz_v \cdot w,而 vv 子树里距离余数为 rr 的点到 uu 的余数变成 (r+w) mod 16(r + w) \bmod 16,故 fu,(r+w) mod 16+=fv,rf_{u,(r+w) \bmod 16} \mathrel{+}= f_{v,r}。
  2. 自顶向下(换根)。设 gug_u、hu,rh_{u,r} 为全树对应的两个量。由父亲 pp 推儿子 uu(边权 ww,e=w mod 16e = w \bmod 16):先扣掉子树 uu 在 pp 处的贡献得到「外部点」的分布 restj=hp,j−fu,(j−e) mod 16rest_j = h_{p,j} - f_{u,(j-e) \bmod 16},这些点到 uu 的距离各多走 ww,于是 hu,r=fu,r+rest(r−e) mod 16h_{u,r} = f_{u,r} + rest_{(r-e) \bmod 16};距离和则是子树内 szusz_u 个点各减 ww、外部 n−szun - sz_u 个点各加 ww,即 gu=gp+(n−2szu) wg_u = g_p + (n - 2sz_u)\,w。

最后按上面的式子结算 SiS_i。注意 j=ij = i 这一项:它的 dis=0dis = 0,在 r=0r = 0 的桶里,题面只要「其他星球」,所以结算时把 r=0r = 0 桶减 1(即自己贡献 00)。

关于素材:本题素材源带有 data.py 数据生成脚本,data/ 是自造的(10 个点由 std.cpp 产出答案,覆盖 n=1n = 1、链、菊花、完全二叉树、随机树与顶格 n=105,M=15n = 10^5, M = 15)。题面系网络重建,与官方原题(同源的「小奇的仓库 / warehouse」)在「是否统计自己」这一细节上以素材数据为准——实测 10 个点全部与「自己贡献 0」的写法一致。本解法的 main.cpp 与 main.py 均按此写法,已逐点通过 data/ 的 10 组数据。

代码

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-08 01:19
# update_at: 2026-10-08 01:19

import sys

K = 16  # M <= 15 只占二进制低 4 位,于是 dis xor M 的修正只依赖 dis mod 16

# 类型别名:每个点的 16 个余数桶 / 一组整数
type Rows = list[list[int]]
type Ints = list[int]


def rooted_order(adj: list[list[tuple[int, int]]]) -> tuple[Ints, Ints, Ints]:
    """以 1 为根做迭代先序遍历,返回 (先序序列, 父节点, 到父节点的边权)。"""
    n = len(adj) - 1
    parent = [0] * (n + 1)
    pedge = [0] * (n + 1)
    order: Ints = []
    stack = [1]
    seen = [False] * (n + 1)
    seen[1] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v, w in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                pedge[v] = w
                stack.append(v)
    return order, parent, pedge


def subtree_dp(order: Ints, parent: Ints, pedge: Ints) -> tuple[Rows, Ints, Ints]:
    """自底向上汇总:返回 (子树余数分布, 子树距离和, 子树大小)。"""
    n = len(parent) - 1
    cnt: Rows = [[0] * K for _ in range(n + 1)]  # cnt[u][r]:子树 u 内到 u 距离 mod 16 == r 的点数
    sub: Ints = [0] * (n + 1)                    # sub[u]:子树 u 内到 u 的距离之和
    size: Ints = [1] * (n + 1)
    for u in range(1, n + 1):
        cnt[u][0] = 1                            # 只有自己,距离 0

    for u in reversed(order[1:]):                # 逆先序:儿子一定先于父亲被汇总
        p = parent[u]
        w = pedge[u]
        e = w % K
        sub[p] += sub[u] + size[u] * w
        size[p] += size[u]
        rot = cnt[u][-e:] + cnt[u][:-e] if e else cnt[u]  # 子树 u 的点到 p 的距离余数整体后移 e
        cnt[p] = [x + y for x, y in zip(cnt[p], rot)]
    return cnt, sub, size


def reroot_dp(order: Ints, parent: Ints, pedge: Ints, cnt: Rows, sub: Ints,
              size: Ints) -> tuple[Rows, Ints]:
    """换根:由父亲的全树信息推出儿子的全树信息,返回 (全树余数分布, 全树距离和)。"""
    n = len(parent) - 1
    dist: Rows = [None] * (n + 1)  # dist[u][r]:全树中到 u 距离 mod 16 == r 的点数
    total: Ints = [0] * (n + 1)    # total[u]:全树所有点到 u 的距离之和
    dist[1] = cnt[1]
    total[1] = sub[1]

    for u in order[1:]:            # 先序:处理 u 时父亲的全树信息已经算好
        p = parent[u]
        w = pedge[u]
        e = w % K
        rot = cnt[u][-e:] + cnt[u][:-e] if e else cnt[u]  # 子树 u 在 p 的余数桶里的贡献
        rest = [x - y for x, y in zip(dist[p], rot)]      # 扣掉子树 u 后,外部点到 p 的分布
        shift = rest[-e:] + rest[:-e] if e else rest      # 外部点到 u 的距离各多走 w
        dist[u] = [x + y for x, y in zip(cnt[u], shift)]
        total[u] = total[p] + (n - 2 * size[u]) * w       # 子树内各减 w,外部各加 w
    return dist, total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b, c = next(data), next(data), next(data)
        adj[a].append((b, c))
        adj[b].append((a, c))

    order, parent, pedge = rooted_order(adj)
    cnt, sub, size = subtree_dp(order, parent, pedge)
    dist, total = reroot_dp(order, parent, pedge, cnt, sub, size)

    delta = [(r ^ m) - r for r in range(K)]  # 把 dis xor M 拆成 dis 加上这个修正量
    out: list[str] = []
    for u in range(1, n + 1):
        d = dist[u]
        # 距离 0 的点就是 u 自己,题面只统计「其他星球」,故在 r == 0 桶里扣掉它
        ans = total[u] + sum(delta[r] * (d[r] - (1 if r == 0 else 0)) for r in range(K))
        out.append(str(ans))
    print('\n'.join(out))


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-08 01:19
 * update_at: 2026-10-08 01:19
 */

// 1771 仓库选址:树上换根 DP + 按位异或的低位拆分
// 因为 M <= 15,异或只作用于距离的二进制低 4 位,于是
//     dis xor M = dis + ((dis mod 16) xor M) - (dis mod 16)
// 只要同时维护「距离和」与「距离 mod 16 的分布」就能 O(16n) 求全部答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100005; // 节点数上限
const int K = 16;        // 距离取模的模数,也是余数桶个数(M <= 15 只占低 4 位)

struct Edge {
    int to;  // 边的另一端
    int nxt; // 同一起点的下一条边编号,0 表示没有
    ll w;    // 边权(航线长度)
};

Edge edge[2 * MAXN]; // 无向边存两条
int head[MAXN];      // head[u] 为 u 的第一条边编号
int edge_cnt;        // 已经加入的边数

int n;      // 星球数
ll M;       // 题目常数 M
ll delta[K]; // delta[r] = (r xor M) - r,把异或改写成加减法的修正量

int parent_[MAXN]; // parent_[u]:u 在 1 号点为根的树中的父亲
ll pedge[MAXN];    // pedge[u]:u 到父亲的边权
int order_[MAXN];  // 先序遍历序列,父亲一定排在儿子前面
int order_cnt;
bool vis[MAXN];
int stack_[MAXN]; // 迭代 DFS 的显式栈,避免递归在链状树上爆栈

ll sub_sum[MAXN];    // sub_sum[u]:u 的子树内所有点到 u 的距离之和
int sub_size[MAXN];  // sub_size[u]:u 的子树大小
ll sub_cnt[MAXN][K]; // sub_cnt[u][r]:u 的子树内到 u 距离 mod 16 == r 的点数

ll all_sum[MAXN];    // all_sum[u]:全树所有点到 u 的距离之和
ll all_cnt[MAXN][K]; // all_cnt[u][r]:全树中到 u 距离 mod 16 == r 的点数

// 加一条无向边
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    edge[edge_cnt].to = v;
    edge[edge_cnt].w = w;
    edge[edge_cnt].nxt = head[u];
    head[u] = edge_cnt;
}

// 迭代先序遍历定根,得到 parent_ / pedge / order_(不用递归,避免链状数据爆栈)
void build_order() {
    int top = 0;
    vis[1] = true;
    stack_[top++] = 1;
    while (top > 0) {
        int u = stack_[--top];
        order_[++order_cnt] = u;
        for (int e = head[u]; e != 0; e = edge[e].nxt) {
            int v = edge[e].to;
            if (vis[v]) continue;
            vis[v] = true;
            parent_[v] = u;
            pedge[v] = edge[e].w;
            stack_[top++] = v;
        }
    }
}

// 自底向上汇总子树信息:距离和 sub_sum 与余数分布 sub_cnt
void subtree_dp() {
    for (int u = 1; u <= n; ++u) {
        sub_size[u] = 1;
        sub_sum[u] = 0;
        sub_cnt[u][0] = 1; // 只有自己,距离 0
    }
    // 逆先序保证处理 u 时它的儿子都已汇总完毕
    for (int idx = order_cnt; idx >= 2; --idx) {
        int u = order_[idx];
        int p = parent_[u];
        ll w = pedge[u];
        int e = w % K;
        sub_sum[p] += sub_sum[u] + sub_size[u] * w; // 子树 u 的点到 p 都要多走 w
        sub_size[p] += sub_size[u];
        for (int r = 0; r < K; ++r) {
            sub_cnt[p][(r + e) % K] += sub_cnt[u][r]; // 子树 u 的点到 p 的距离多走 w
        }
    }
}

// 自顶向下换根:由父亲 p 的全树信息推出儿子 u 的全树信息
void reroot_dp() {
    all_sum[1] = sub_sum[1];
    for (int r = 0; r < K; ++r) all_cnt[1][r] = sub_cnt[1][r];

    for (int idx = 2; idx <= order_cnt; ++idx) {
        int u = order_[idx];
        int p = parent_[u];
        ll w = pedge[u];
        int e = w % K;
        ll rest[K]; // 全树去掉 u 子树后,剩下的点到 p 的距离余数分布
        for (int j = 0; j < K; ++j) {
            // 子树 u 在 p 处的余数桶里落在 (j - e) mod K,扣掉它才是「外部点」
            rest[j] = all_cnt[p][j] - sub_cnt[u][((j - e) % K + K) % K];
        }
        for (int r = 0; r < K; ++r) {
            // 外部点到 u 的距离 = 到 p 的距离 + w,余数整体后移 e
            all_cnt[u][r] = sub_cnt[u][r] + rest[((r - e) % K + K) % K];
        }
        // 外部点(n - sub_size[u] 个)距离各加 w,子树内点(sub_size[u] 个)各减 w
        all_sum[u] = all_sum[p] + (n - 2 * sub_size[u]) * w;
    }
}

int main() {
    if (scanf("%d %lld", &n, &M) != 2) return 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        ll c;
        scanf("%d %d %lld", &a, &b, &c);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }

    for (int r = 0; r < K; ++r) delta[r] = (r ^ M) - r;

    build_order();
    subtree_dp();
    reroot_dp();

    for (int u = 1; u <= n; ++u) {
        ll ans = all_sum[u];
        for (int r = 0; r < K; ++r) {
            // 距离 0 的那个点就是 u 自己,题面只统计「其他星球」,要扣掉
            ll cnt = all_cnt[u][r] - (r == 0 ? 1 : 0);
            ans += delta[r] * cnt;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

复杂度

  • 时间复杂度:两趟 DFS 各自对每条边合并 16 个余数桶,结算每个点扫 16 个桶,总计 O(16n)O(16n)。n=105n = 10^5 时约 5×1065 \times 10^6 次基本操作,远小于 1000 ms 的时限。
  • 空间复杂度:邻接表 O(n)O(n),每个点 16 个余数桶(子树一套、全树一套),总计 O(16n)O(16n),n=105n = 10^5 时约 20 MB,低于 256 MB。

总结

  • 本题的关键是「M⩽15M \leqslant 15 意味着异或只影响低 4 位」,从而把 dis⊕Mdis \oplus M 拆成 disdis 加上一个只依赖 dis mod 16dis \bmod 16 的修正量,把非线性的异或问题降维成 16 个可换根维护的计数桶。
  • 这类「⊕\oplus 只影响低位」的拆分在树上、区间上反复出现,只要注意到模 2k2^k 与异或的配合,就能把异或和转成普通的和 + 分类计数。
  • 树上「对每个点求全树统计量」的模板就是换根 DP:先自底向上求子树信息,再自顶向下扣子树、补外部。树深度可达 nn,实现时用显式栈迭代而不是递归。