题解 | #路径数目#

题意

给定一颗树，每个节点有一个0/1的值。求有多少个叶节点满足根节点到叶节点的路径上的点的值之和不大于2.

思考

因为每个节点的值是非负的(所以走必须经过路径外的点并不会使答案更优)。所以从根节点到叶节点的最小路径是确定的，就是一直向下的那条路径。

方法一(bfs)

这明显就是个求给定多个点中离根节点最近的点的题。所以我们可以用bfs算法求出距离(不用floyd不只是因为时间复杂度，还是因为我们这里的长度体现在节点上，所以floyd比较难处理)，然后找出所有的叶子节点，统计不大于2的点就可以了。

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
const int N = 200001;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 一个整数，表示路径数
     * @param n int 
     * @param Edge Pointvector 
     * @param f intvector 
     * @return int
     */
    int head [N],nxt [N << 1],v [N << 1],cnt;
    int dp [N];
    bool vis [N];    //防止访问父亲 
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        memset(head,0,sizeof head);
        memset(nxt,0,sizeof nxt);
        memset(dp,0,sizeof dp);
        memset(vis,0,sizeof vis);
        cnt = 0;
        for (auto &l:Edge) {
            l.x --;l.y --;
            nxt [++ cnt] = head [l.x];
            head [l.x] = cnt;
            v [cnt] = l.y;
            nxt [++ cnt] = head [l.y];
            head [l.y] = cnt;
            v [cnt] = l.x;
        }
        queue<int> p;
        p.push(0);
        dp [0] = f [0];
        int ans = 0;
        while (!p.empty()) {
            int i = p.front();p.pop();
            vis [i] = true;
            if (dp [i] > 2) continue ;
            bool isLeaf = true;    //是不是叶子节点 
            for (int ptr = head [i];ptr;ptr = nxt [ptr]) {
                int vv = v [ptr];
                if (vis [vv]) continue ;
                isLeaf = false;    //有其他儿子，那就不是叶子节点
                dp [vv] = dp [i] + f [vv];
                p.push(vv); 
            }
            if (isLeaf) ++ ans;
        }
        return ans;
    }
};

因为每个节点出队入队一次，所以时间复杂度为 $O(n)$ ，且储存了树的图结构，所以空间复杂度为 $O(n)$ 。

方法二

我们也可以考虑直接DFS，求出到达每个节点的最小路径值，统计答案即可。

dfs的状态为到达某一节点的最小值.(图中不同颜色代表不同的dfs分支)

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
const int N = 200001;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 一个整数，表示路径数
     * @param n int 
     * @param Edge Pointvector 
     * @param f intvector 
     * @return int
     */
    int head [N],nxt [N << 1],v [N << 1],cnt;
    int pv [N];
    int dfs (int i,int fa,int num) {
        num += pv [i]; //路径上的点也包括自己本身
        if (num > 2) return 0;     //剪枝
        bool haveSon = false;
        int ans = 0;
        for (int ptr = head [i];ptr;ptr = nxt [ptr]) {
            if (v [ptr] == fa) continue ;    //防止循环
            haveSon = true;    //不是叶子节点(因为有其他儿子)
            ans += dfs (v [ptr],i,num);
        }
        if (!haveSon) return 1;    //到达叶子节点(因为没有其他儿子了) 
        return ans;
    }
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        memset(head,0,sizeof head);
        memset(nxt,0,sizeof nxt);
        cnt = 0;
        for (auto &l:Edge) {
            l.x --;l.y --;
            nxt [++ cnt] = head [l.x];
            head [l.x] = cnt;
            v [cnt] = l.y;
            nxt [++ cnt] = head [l.y];
            head [l.y] = cnt;
            v [cnt] = l.x;
        }
        for (int i = 0;i < n;++ i) {
            pv [i] = f [i];
        }
        return dfs (0,0,0);
    }
};

因为是对树进行dfs，且每个节点只访问了一次。

所以可以得出时间复杂度为 $O(n)$ 。

而我们只储存了树的边，所以空间复杂度为 $O(log(n))$ 。