题目解法：基环树上的树形 DP

问题分析

题目要求对基环树染色，使得每个点恰有一个相邻点被染色（不包括自身）。这是一个基环树上的约束满足问题。

关键性质

基环树结构：$n$ 个点 $n$ 条边的连通图，包含恰好一个环

约束条件：每个点的染色邻居数必须恰好为 1

环的处理：环上的约束是全局性的，需要特殊处理

算法思路

1.基环树识别

使用并查集找出环上的一条边 (keyu, keyv)

将这条边暂时移除，得到一棵树

2.树形 DP 状态设计

对于每个节点 $x$，定义状态：

• f[x][p][q]：表示以 $x$ 为根的子树中

• p：$x$ 是否被染色（0/1）

• q：$x$ 的父节点是否被染色（0/1）

• 值表示该状态下子树中最少染色点数

3.状态转移

对于普通节点：

如果 $x$ 染色：子节点都不能染色，且 $x$ 的染色邻居只能来自父节点

如果 $x$ 不染色：子节点中必须恰好有一个染色

对于环上的特殊节点：

需要额外考虑环的连通性约束

通过 opt 枚举环上相邻点的染色状态

4.环的处理

枚举环上边 (keyu, keyv) 两端点的染色情况：

• opt = 0：两个端点都不染色

• opt = 1：keyu 染色

• opt = 2：keyv 染色

• opt = 3：两个端点都染色

对每种情况分别 DP，取最小值。

复杂度分析

• 并查集找环：$O(n\alpha(n))$

• 树形 DP：$O(n)$

• 枚举环上状态：$O(4n)$

总复杂度：$O(n)$，可过 $n \leq 10^5$

代码亮点

状态设计巧妙：f[x][p][q] 同时记录当前点和父节点状态

环的枚举：通过 opt 位运算枚举环上约束

边界处理：对自环和相邻环边的特殊处理

无解判断：当答案 $> n$ 时判定无解

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace fastIO {
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -f;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}
int buf[20], TOT;
inline void print(int x, char ch = ' ') {
    if (x < 0)
        putchar('-'), x = -x;
    else if (x == 0)
        buf[++TOT] = 0;

    for (int i = x; i; i /= 10)
        buf[++TOT] = i % 10;

    do {
        putchar(buf[TOT] + '0');
    } while (--TOT);

    putchar(ch);
}
}
using namespace fastIO;
const int MAXN = 1e5 + 5, inf = 1e9;
int n, keyu, keyv;
int fa[MAXN];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
vector<int> e[MAXN];

int f[MAXN][2][2], opt;
void dfs(int x, int dad) {
    if (x == keyu || x == keyv) {
        int op = 0;

        if (x == keyu && (opt & 1))
            op = 1;

        if (x == keyv && (opt & 2))
            op = 1;

        if (op) {
            f[x][1][0] = 1;

            for (int to : e[x]) {
                if (to == dad)
                    continue;

                dfs(to, x);
                f[x][1][1] = min(f[x][1][1] + f[to][0][0], f[x][1][0] + f[to][1][0]);
                f[x][1][0] += f[to][0][0];
            }

            if (opt == 3) {
                f[x][1][1] = f[x][1][0];
                f[x][1][0] = inf;
            }
        } else {
            f[x][0][0] = 0;

            for (int to : e[x]) {
                if (to == dad)
                    continue;

                dfs(to, x);
                f[x][0][1] = min(f[x][0][1] + f[to][0][1], f[x][0][0] + f[to][1][1]);
                f[x][0][0] += f[to][0][1];
            }

            if (x == keyu && (opt & 2)) {
                f[x][0][1] = f[x][0][0];
                f[x][0][0] = inf;
            }

            if (x == keyv && (opt & 1)) {
                f[x][0][1] = f[x][0][0];
                f[x][0][0] = inf;
            }
        }
    } else {
        f[x][0][0] = 0;
        f[x][1][0] = 1;

        for (int to : e[x]) {
            if (to == dad)
                continue;

            dfs(to, x);
            f[x][0][1] = min(f[x][0][1] + f[to][0][1], f[x][0][0] + f[to][1][1]);
            f[x][0][0] += f[to][0][1];
            f[x][1][1] = min(f[x][1][1] + f[to][0][0], f[x][1][0] + f[to][1][0]);
            f[x][1][0] += f[to][0][0];
        }
    }
}
signed main() {
    n = read();

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    for (int i = 1; i <= n; i++) {
        int u = read(), v = read();

        if (find(u) == find(v)) {
            keyu = u, keyv = v;
        } else {
            e[u].push_back(v);
            e[v].push_back(u);
            fa[find(u)] = find(v);
        }
    }

    bool flag = 0;

    for (int to : e[keyu])
        if (to == keyv)
            flag = 1;

    if (flag || keyu == keyv) {
        for (int i = 1; i <= n; i++)
            for (int p = 0; p < 2; p++)
                for (int q = 0; q < 2; q++)
                    f[i][p][q] = inf;

        keyu = keyv = 0;
        dfs(1, 0);
        int ans = inf;
        ans = min(f[1][0][1], f[1][1][1]);

        if (ans > n)
            print(-1);
        else
            print(ans);
    } else {
        int ans = inf;

        for (opt = 0; opt < 4; opt++) {
            for (int i = 1; i <= n; i++)
                for (int p = 0; p < 2; p++)
                    for (int q = 0; q < 2; q++)
                        f[i][p][q] = inf;

            dfs(keyu, 0);

            for (int p = 0; p < 2; p++)
                ans = min(ans, f[keyu][p][1]);
        }

        if (ans > n)
            print(-1);
        else
            print(ans);
    }

    return 0;
}