RT，根据紫书上的写法，写了树形dfs-dp和dfs序-dp两种写法，为什么一个AC一个WA？

第一份：AC的树形dfs-dp的写法：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXN 10010
#define INF 10010
using namespace std;

vector<int> G[MAXN];
int dp[MAXN][3];

inline int read() {
    register int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void dfs(int u, int fa) {
    for (int i = 0; i < G[u].size(); i++) {
        int to = G[u][i];
        if (to == fa) continue;
        dfs(to, u);
        dp[u][0] += min(dp[to][0], dp[to][1]);
        dp[u][1] += dp[to][2];
        if (dp[u][0] > 10010) dp[u][0] = 10010;
        if (dp[u][1] > 10010) dp[u][1] = 10010;
    }
    for (int j = 0; j < G[u].size(); j++) {
        int to = G[u][j];
        if (to == fa) continue;
        //if (dp[to][2] != INF)
            dp[u][2] = min(dp[u][2], dp[u][1] - dp[to][2] + dp[to][0]);
        if (dp[u][2] > 10010) dp[u][2] = 10010;
    }
    return;
}

int n;
int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            G[i].clear();
        for (int i = 0; i <= n + 1; i++) {
            dp[i][0] = 1;
            dp[i][1] = 0;
            dp[i][2] = INF;
        }
        for (int i = 1; i < n; i++) {
            int x = read(), y = read();
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1, -1);
        printf("%d\n", min(dp[1][0], dp[1][2]));
        int x = read();
        if (x == -1) break;
    }
    return 0;
}
/*
6
1 3
2 3
3 4
4 5
4 6
0
2
1 2
-1
*/

第二份：根据紫书提示：运用dfs序 + 遇到超过INF就判断越界，但是遇到大数据还是输出一堆负数：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXN 10010
#define INF 10010
using namespace std;

vector<int> G[MAXN], dfs_xu, son[MAXN];
int dp[MAXN][3];

inline int read() {
    register int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void dfs(int u, int fa) {
    dfs_xu.push_back(u);
    for (int i = 0; i < G[u].size(); i++) {
        int to = G[u][i];
        if (to == fa) continue;
        son[u].push_back(to);
        dfs(to, u);
    }
    return;
}

int n;
int main() {
    //freopen("UVA1218.in", "r", stdin);
    //freopen("UVA1218.out", "w", stdout);
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            son[i].clear();
            G[i].clear();
        }
        dfs_xu.clear();
        for (int i = 0; i <= n + 1; i++) {
            dp[i][0] = 1;
            dp[i][1] = 0;
            dp[i][2] = INF;
        }
        for (int i = 1; i < n; i++) {
            int x = read(), y = read();
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1, -1);
        for (int j = dfs_xu.size() - 1; j >= 0; j--) {
            int u = dfs_xu[j];
            for (int i = 0; i < son[u].size(); i++) {
                int to = son[u][i];
                dp[u][0] += min(dp[to][0], dp[to][1]);
                dp[u][1] += dp[to][2];
            }
            if (dp[u][0] > 10010) dp[u][0] = 10010;
            if (dp[u][1] > 10010) dp[u][1] = 10010;
            for (int i = 0; i < son[u].size(); i++) {
                int to = G[u][i];
                //if (dp[to][2] != INF)
                    dp[u][2] = min(dp[u][2], dp[u][1] - dp[to][2] + dp[to][0]);
            }
            if (dp[u][2] > 10010) dp[u][2] = 10010;
        }
        printf("%d\n", min(dp[1][0], dp[1][2]));
        int x = read();
        if (x == -1) break;
    }
    return 0;
}
/*
6
1 3
2 3
3 4
4 5
4 6
0
2
1 2
-1
*/

谢谢各位大佬，不要冷场谢谢