题解：P14455 [ICPC 2025 Xi'an R] Imagined Holly

Eason_cyx · 2026-07-25 18:52:31 · 题解

思考这个 a 数组的本质，如果给定一棵树，我们要如何求出两点 u,v 路径上的所有点的异或和？如果设 S_u 表示从根到 u 路径上所有点的异或和，那么就有

移项得到：

也就是说，我们如果随便钦定一个跟，那么久可以通过 a 数组，求出树上两两点之间的 \text{LCA}。那求出来之后能干什么呢？显然我们可以得到一个点的所有祖先，假设一个点有 c 个祖先，则我们在其祖先中找到一个有 c-1 个祖先的点就是其父亲。

然后直接输出即可。时间复杂度 O(n^2)。

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int a[N][N], l[N][N];
bool f[N][N]; int cnt[N], fa[N];
int main() {
    int n; cin >> n;
    for(int i = 1;i <= n;i++)
        for(int j = i;j <= n;j++)
            cin >> a[i][j],
            a[j][i] = a[i][j];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            l[i][j] = (i == j ? i : (a[i][j] ^ a[1][i] ^ a[1][j]));
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++)
            if(!f[i][l[i][j]])
                f[i][l[i][j]] = 1, cnt[i]++;
    } for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++)
            if(cnt[l[i][j]] == (cnt[i] - 1))
                fa[i] = l[i][j];
    } for(int i = 2;i <= n;i++)
        cout << i << " " << fa[i] << endl;
    return 0;
}