Solution
如果以 \(1\) 为根节点，就只需找到 \(2\sim n\) 号节点的父亲。而一个节点的父亲节点就是其所有祖先中子树大小最小的节点，我们就可以利用这个特点完成此题。
对于两个节点 \(i,j\) ，显然有 \(a_{i,j} = a_{1,i} \oplus a_{1,j} \oplus \mathtt{LCA(i,j)}\) ，也就是说由此可得任意两点的 \(\mathtt{LCA(i,j)} = a_{i,j} \oplus a_{1,i} \oplus a_{1,j}\) 。
那么对于一个子树 \(i\) ，在此子树的节点 \(j\) 满足 \(\mathtt{LCA(i,j)} = i\) ，所以只需统计满足 \([\mathtt{LCA(i,j)} = i]\) 的 \(j\) 的个数就能得到子树 \(i\) 的大小。
得到所有子树大小后，对于 \(2\sim n\) 号节点，在其所有祖先中找到子树大小最小的节点，就是其父亲节点了。
时间复杂度 \(\mathcal{O(n^2)}\)
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,a[N][N],fa[N],lca[N][N],sz[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){scanf("%d",&a[i][j]),a[j][i]=a[i][j];lca[j][i]=lca[i][j]=a[1][i]^a[1][j]^a[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(lca[i][j]==i)sz[i]++;sz[0]=n+1;for(int i=2;i<=n;i++){int f=0;for(int j=1;j<=n;j++)if(j!=i&&lca[i][j]==j)if(sz[j]<sz[f])f=j;fa[i]=f;}for(int i=2;i<=n;i++)printf("%d %d\n",fa[i],i);return 0;
}