思路与算法

先按根深度和子树规模换根求原始距离和。源数据表M最大15，只改动距离低4位，建立每个点到全部点距离模16的计数直方图：后序合并子树直方图，再前序把父侧贡献平移并扣除原子树贡献。对M中置1的每位b，按n-2×该位为1的距离数修正2^b；最后减掉自身0 xor M的M。

正确性说明

异或置1的位把0变1、1变0，修正量正是2^b(零数-一数)。模16保留全部会改变的位。换根直方图对孩子内部直接取down，对外部从父直方图减去孩子原贡献后统一加边长，按距离的唯一分解不重不漏；原距离和加修正并排除自身即答案。

复杂度

读入、树数组初始化O(N)，两个直方图各16N初始化与转移，原距离和换根O(N)，总O(16N)时间、O(16N)空间；遍历迭代无深栈。

易错点

M=0为公开样例合法情况。源数据表只覆盖0到15，不能把此标程宣称支持任意高位M。边权为正且答案≤2×10^9，64位计算中间距离和；自身不属于其他星球，必须减M。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long M;
    cin >> n >> M;
    vector<vector<pair<int, long long>>> g(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        g[--a].push_back({--b, w});
        g[b].push_back({a, w});
    }
    vector<int> par(n, -1), sz(n, 1), ord(1, 0);
    vector<long long> w(n), dist(n), raw(n);
    vector<array<int, 16>> down(n), all(n);
    for (auto &a : down) {
        a.fill(0);
        a[0] = 1;
    }
    for (size_t i = 0; i < ord.size(); i++) {
        int u = ord[i];
        for (auto e : g[u])
            if (e.first != par[u]) {
                par[e.first] = u;
                w[e.first] = e.second;
                dist[e.first] = dist[u] + e.second;
                ord.push_back(e.first);
            }
    }
    raw[0] = accumulate(dist.begin(), dist.end(), 0LL);
    for (int i = n - 1; i > 0; i--) {
        int u = ord[i], p = par[u], z = w[u] % 16;
        sz[p] += sz[u];
        for (int r = 0; r < 16; r++)
            down[p][(r + z) % 16] += down[u][r];
    }
    all[0] = down[0];
    for (int i = 1; i < n; i++) {
        int u = ord[i], p = par[u], z = w[u] % 16;
        raw[u] = raw[p] + (n - 2LL * sz[u]) * w[u];
        for (int r = 0; r < 16; r++)
            all[u][r] = down[u][r] + all[p][(r - z + 16) % 16] - down[u][(r - 2 * z + 32) % 16];
    }
    for (int u = 0; u < n; u++) {
        long long ans = raw[u] - M;
        for (int b = 0; b < 4; b++)
            if (M >> b & 1) {
                int cnt = 0;
                for (int r = 0; r < 16; r++)
                    if (r >> b & 1)
                        cnt += all[u][r];
                ans += (1LL << b) * (n - 2LL * cnt);
            }
        cout << ans << '\n';
    }
}