题目理解

树镜像图由两棵相同的有根树 $T$ 和 $S$ 通过合并对应叶节点得到。图中有两个特殊的节点（两个根），其余叶节点成对合并。

算法思路

代码的核心思路是：

1. 寻找可能的两个根节点
2. 从这两个根出发验证图是否对称

代码详细解析

1. 数据结构定义

const int MAXN = 1e5 + 5;
int n, m, fa[MAXN];
bool vis[MAXN], inc[MAXN];
vector <int> G[MAXN], rt, cyc;

• fa[]: DFS 父节点记录
• vis[]: 访问标记
• inc[]: 是否在环中
• rt: 存储候选根节点
• cyc: 存储找到的环

2. 第一步：寻找候选根

情况1：存在度数为1的节点

for (int i = 1; i <= n; ++i)
    if (G[i].size() == 1)
        rt.push_back(i);

如果存在度数为1的节点，它们很可能是根节点（在原树中根可能度数任意，但在合并后的图中，如果原树根度数为1，则它在图中度数也为1）。

情况2：没有度数为1的节点

此时图可能是一个环，或者环上挂子树：

dfs1(1, 0);  // 找环
if (cyc.empty() || count(vis + 1, vis + n + 1, 0))
    return cout << "NO\n", 0;

• dfs1: 找图中的环
• 如果找不到环或不连通，直接输出NO

3. DFS1：找环算法

void dfs1(int u, int fz) {
    vis[u] = true, fa[u] = fz;
    for (int v : G[u])
        if (v ^ fz) {
            if (!vis[v])
                dfs1(v, u);
            else if (cyc.empty()) {  // 找到第一个环
                for (int x = u; x != v; x = fa[x])
                    cyc.push_back(x);
                cyc.push_back(v);
            }
        }
}

标准DFS找环算法，记录环上节点到cyc中。

4. DFS2：从非环节点找根

void dfs2(int u) {
    vis[u] = true;
    if (inc[u])  // 遇到环上的节点，作为候选根
        return rt.push_back(u);
    for (int v : G[u])
        if (!vis[v])
            dfs2(v);
}

从不在环上的节点出发，找到的第一个环节点作为候选根。

5. 核心验证函数 chk(x, y)

5.1 BFS计算距离

bfs(x, dx), bfs(y, dy);

从两个候选根分别BFS，计算到所有节点的距离。

5.2 分配节点归属

for (int i = 1; i <= n; ++i) {
    if (dx[i] < dy[i]) fy[i] = -1, --sy;  // 属于x的树
    if (dx[i] > dy[i]) fx[i] = -1, --sx;  // 属于y的树
}

• 离x更近的节点属于x的树
• 离y更近的节点属于y的树
• 距离相等的节点是合并的叶节点

5.3 验证树结构

dfs3(x, 0, fx), dfs3(y, 0, fy);

验证每个子树确实是树结构（无环）。

5.4 验证对称性

for (int i = 1, ct = 0; i <= n; ++i)
    if (dx[i] == dy[i]) {  // 合并的叶节点
        for (int u = i, v = i; u; u = fx[u], v = fy[v]) {
            if (w[u] != w[v]) return false;  // 对称位置必须相同
            if (!w[u]) w[u] = w[v] = ++ct;   // 标记对称对
            else break;
        }
    }

关键部分：验证对称位置的节点具有相同的结构。

6. 特殊情况处理

cout << (n & 1 ? "NO\n" : "YES\n");

如果所有节点都在环上，只有当节点数为偶数时才可能是镜像图。

算法复杂度

• BFS/DFS: $O(n + m)$
• 总体复杂度: $O(n + m)$

正确性证明要点

1. 根的选择：根必须是度数为1的节点，或者是环上的节点（当没有度数为1的节点时）
2. 距离划分：离哪个根更近就属于哪棵树
3. 对称验证：距离相等的节点必须成对对称
4. 树结构验证：确保每部分确实是树

样例验证

样例2 (输出YES):

6 6
1 2
2 3  
2 4
3 5
4 5
5 6

• 候选根：1和6（度数为1）
• 验证对称性通过

样例1 (输出NO):

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

• 是一个环，节点数奇数
• 不满足对称条件

这个算法通过系统性的根候选选择和对称性验证，能够正确判断任意图是否为树镜像图。