M≤15 时异或只改距离的低 4 位,用换根 DP 同时维护距离和与距离 mod 16 的分布,O(16n) 求出每点到全树的花费之和。
OJ: roj
题目 ID: 1771
难度:提高
标签:动态规划换根DP位运算树python
创建: 2026-10-08 01:19
更新: 2026-10-08 01:19
形式化题目
给一棵
其中
数据规模:
正解
思路
先看暴力:对每个
瓶颈在于「每个点都要一遍全树」,而树上这类「对每个点求全树统计量」的问题有标准武器——换根 DP。但直接换根只能维护距离和
突破口是数据范围里的
由于
又因为
这一步把「非线性的异或」换成了「距离本身 + 一个只依赖
左边是标准的「全树距离和」,右边只需要「距离模 16 的分布」——只有 16 个桶。两个量都能换根 DP 维护,于是复杂度降到
具体做法分两趟 DFS(这里全部写成迭代,避免链状数据爆栈):
- 自底向上(子树 DP)。定根为 1。对每个
维护 (子树内到 的距离和)、 (子树大小)、 (子树内到 距离 的点数,含 自身)。合并儿子 (边权 )时: , ,而 子树里距离余数为 的点到 的余数变成 ,故 。 - 自顶向下(换根)。设
、 为全树对应的两个量。由父亲 推儿子 (边权 , ):先扣掉子树 在 处的贡献得到「外部点」的分布 ,这些点到 的距离各多走 ,于是 ;距离和则是子树内 个点各减 、外部 个点各加 ,即 。
最后按上面的式子结算
关于素材:本题素材源带有
data.py数据生成脚本,data/是自造的(10 个点由std.cpp产出答案,覆盖、链、菊花、完全二叉树、随机树与顶格 )。题面系网络重建,与官方原题(同源的「小奇的仓库 / warehouse」)在「是否统计自己」这一细节上以素材数据为准——实测 10 个点全部与「自己贡献 0」的写法一致。本解法的 main.cpp与main.py均按此写法,已逐点通过data/的 10 组数据。
代码
#!/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()/**
* 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 个桶,总计
。 时约 次基本操作,远小于 1000 ms 的时限。 - 空间复杂度:邻接表
,每个点 16 个余数桶(子树一套、全树一套),总计 , 时约 20 MB,低于 256 MB。
总结
- 本题的关键是「
意味着异或只影响低 4 位」,从而把 拆成 加上一个只依赖 的修正量,把非线性的异或问题降维成 16 个可换根维护的计数桶。 - 这类「
只影响低位」的拆分在树上、区间上反复出现,只要注意到模 与异或的配合,就能把异或和转成普通的和 + 分类计数。 - 树上「对每个点求全树统计量」的模板就是换根 DP:先自底向上求子树信息,再自顶向下扣子树、补外部。树深度可达
,实现时用显式栈迭代而不是递归。