【牛客编程巅峰赛S1第7场】牛牛打怪兽

题目

牛牛来到训练场里闯关，他的宝剑的耐久度降到了 2，这意味着牛牛最多只能打倒 2 只怪兽，否则将会被淘汰。
训练场的地图可以看作一棵以 1 为根节点的树，训练场的终点为这棵树的叶子结点，树上的每个结点最多有一只怪兽，结点与结点间的边上没有怪兽。
每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全，并且牛牛一旦选定好打怪路线之后便不能走回头路。
请问牛牛有多少种到达终点且不被淘汰的路径。

解题思路

使用 DFS 算法。

到达某个点时，判断此时的宝剑耐久度是否大于等于 0 且是否是叶子节点，若是，则累加计入 。

C++代码

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
    int ans = 0;
    vector<vector<int>> edges;
    vector<int> vis;
    void dfs(int a, int cnt, vector<int>& f){
        cnt -= f[a-1];
        if(cnt < 0)
            return;
        bool isLeaf = true;
        for(auto b : edges[a]){
            if(!vis[b]){
                isLeaf = false;
                vis[b] = true;
                dfs(b, cnt, f);
            }
        }
        if(isLeaf)
            ++ans;
    }
public:
    /**
     * 返回牛牛能到达终点且不被淘汰的路径数
     * @param n int整型 
     * @param Edge Point类vector 
     * @param f int整型vector 
     * @return int整型
     */
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        // write code here
        edges.resize(n+1);
        for(int i=0; i<Edge.size(); ++i){
            int u = Edge[i].x;
            int v = Edge[i].y;
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        ans = 0;
        vis.resize(n+1, false);
        vis[1] = true;
        dfs(1, 2, f);
        return ans;
    }
};