这是我写的第8个正式题解

---

【A75466】[GESP202409 七级] 小杨寻宝

题目链接

点这里

题目大意

有一棵 $n$ 个节点，$n-1$ 条边的树
可以任意选择起点并在树上移动
但是：只能经过每条边 $1$ 次（也就是说必须要走简单路径）
树上有一些节点被放置了宝物，如果到达这些节点，将会获得这个宝物
问：能否取得所有宝物

解题思路

1. 算法选择

dfs+bfs

2.1. 核心思路

• dfs+记忆化
  构造一个新的数组dis，数组的每一个节点代表树上相对应节点的子树中有多少个宝藏
• 根据dis数组枚举
  找到根节点
• bfs
  对每个节点做判断（如果其同时拥有 $2$ 条以上的宝藏分支，则整体不合法，能全部遍历完则合法）

2.2. 具体、详细的思路

dfs+记忆化

• dfs(u, fa)，代表当前节点为u,其父节点为fa
• 定义数组，$dis_i$ 的值表示树上编号为 $i$ 的节点的子树中有的宝藏数量
• 如果这个点已经算过了，直接返回答案
• 设置一个cnt变量，代表子树中拥有的宝藏数量。将cnt初始值设为 $a_u$
• 遍历当前节点连接的所有邻居节点
• • 如果当前节点为父节点，则跳过
• • 否则调用 $dfs(当前节点，u)$
• 返回最终答案
• • 因为我们用的是记忆化的思路，所以应该 return dis[u] = cnt

int dfs(int u, int fa){
    // 1.（记忆化）如果这个点已经算过了，直接返回答案
    if (dis[u] != -1){
        return dis[u];
    }
    // 2.设置初始值
    int cnt = a[u];
    // 3.遍历+递归累加所有节点
    for (int now : g[u]){
        // 必须判断当前遍历到的节点不是父节点（因为存树的时候是无向树，如果不判断将会卡死）
        if (now == fa){
            continue;
        }
        cnt += dfs(now, u);
    }
    // 4.返回最终答案（记忆化真正生效的点是最后dis[u] = sum）
    return dis[u] = cnt;
}

find_root()函数找根节点

因为我们要知道，根节点不一定是 $1$ ，所以需要一个单独的函数找根节点（否则就需要另一个思路）

• 循环u从 $1 \sim n$
• 设置一个cnt变量，记录当前节点 $i$ 有多少个相邻节点是 $dis_i > 0$ 的
• • 因为合法路径一定是一条链，所有宝物都在这条链上，所以链的端点一定满足：最多只有 1 个方向存在宝物。
• • 如果当前节点 $i$ 对应的 $dis_i > 0$，表示当前节点有 $1$ 个方向存在宝物
• 如果 $cnt <2$ 说明符合链端点条件，选为根
• • 如果当前节点为父节点，则跳过
• • 否则调用 $dfs(当前节点，u)$
• 返回根节点值，若最终无返回则默认节点 $1$ 为根节点

int find_root(){
    // 循环u从1~n
    for(int u = 1; u <= n; u++){
        // 设置cnt
        int cnt = 0;
        // 遍历所有相邻
        for(int v : g[u]){
            if(dis[v] > 0) {
                cnt++;
            }
        }
        // 符合链端点条件，选为根
        if(cnt <= 1){
            return u;
        }
    }
    return 1;
}

bfs

• 建立队列，储存 (当前节点, 父节点)，防止无向树反向走
• 起点（根节点）入队，标记已访问
• 循环取出队首节点 $u$、它的父节点 $fa$
• 设置一个变量has，记录队首节点子树有多少宝藏分支
• 遍历 $u$ 所有相邻点 $now$：
• • 如果 $now$ 是父节点，直接跳过，禁止走回头路
• • 如果 $now$ 的子树有宝藏，宝藏分支计数器 $cnt + 1$
• 没访问过的点，先打标记、再入队，继续遍历
• 对当前点做判断：
• • 同时拥有 2 条及以上宝藏分支，直接判定整体不合法，返回 $false$
• • 全部点遍历完毕无违规，返回 $true$

bool bfs(int s){
    /*
    建立队列，储存 (当前节点, 父节点)，防止无向树反向走。
    起点（根节点）入队，标记已访问。
    循环取出队首节点 u、它的父节点 fa。
    遍历 u 所有相邻点 now：
    如果 now 是父节点，直接跳过，禁止走回头路。
    如果 now 的子树有宝藏，宝藏分支计数器 cnt++。
    没访问过的点，先打标记、再入队，继续向下遍历。
    对当前点做判断：
    同时拥有 2 条及以上宝藏分支 → 直接判定整体不合法，返回 false。
    全部点遍历完毕无违规，返回 true。
    */
    queue<node> q;
    q.push({s, -1});
    vis[s] = true;
    while(!q.empty()){
        int u = q.front().u;
        int fa = q.front().fa;
        q.pop();
        int has = 0;
        for (int now : g[u]){
            /*
            这题遍历中的顺序是：
            1.跳过父节点
            2.统计含有宝藏子树的数量
            3.未访问则标记入队
            */
            if (now == fa){
                continue;
            }
            if (dis[now] >= 1){
                has++;
            }
            if (vis[now]){
                continue;
            }
            q.push({now, u});
            vis[now] = 1;
        }
        if (has >= 2){
            return false;
        }
    }
    return true;
}

3. 复杂度分析

• 时间复杂度：$O(tn)$
• 空间复杂度：$O(n)$

易错点/坑点

1. 循环输入边数范围是：$1 \sim n - 1$
2. 树存储时为无向树

AC 代码

#include <bits/stdc++.h>
using namespace std;

int n, t;
const int N = 1e5 + 10;
int a[N];
vector<int> g[N];
int dis[N];
int dfs(int u, int fa){
    if (dis[u] != -1){
        return dis[u];
    }
    int cnt = a[u];
    for (int now : g[u]){
        if (now == fa){
            continue;
        }
        cnt += dfs(now, u);
    }
    return dis[u] = cnt;
}
int find_root(){
    for(int u = 1; u <= n; u++){
        int cnt = 0;
        for(int v : g[u]){
            if(dis[v] > 0) {
                cnt++;
            }
        }
        if(cnt <= 1){
            return u;
        }
    }
    return 1;
}
int vis[N];
struct node{
    int u;
    int fa;
};
bool bfs(int s){
    queue<node> q;
    q.push({s, -1});
    vis[s] = true;
    while(!q.empty()){
        int u = q.front().u;
        int fa = q.front().fa;
        q.pop();
        int has = 0;
        for (int now : g[u]){
            if (now == fa){
                continue;
            }
            if (dis[now] >= 1){
                has++;
            }
            if (vis[now]){
                continue;
            }
            q.push({now, u});
            vis[now] = 1;
        }
        if (has >= 2){
            return false;
        }
    }
    return true;
}

int main(){

    cin >> t;
    while(t--){
        memset(a, 0, sizeof(a));
        memset(vis, false, sizeof(vis));
        cin >> n;
        for (int i = 1;i <= n;i++){
            cin >> a[i];
            g[i].clear();
            dis[i] = -1;
        }
        for (int i = 1;i < n;i++){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, -1);
        int root = find_root();
        cout << (bfs(root) ? "Yes\n" : "No\n");
    }
    
    return 0;
}