Codeforces - 580C - Kefa and Park

Question

题目大意

题目是给你 n 、 m ， n 代表这个图（一颗生成树) 的顶点个数，然后下面一行 n 个数，代表这个顶点是否有 cat ，现在要从根节点 1 出发，去到叶子节点，但是中间不能有连续 m 个 cat ，问有多少中走法。

解析

这题其实不难，但是一开始看错题目。。。以为是求能到达多少个不是 cat 的节点，结果 wa 很多次。

思路: 直接 dfs ：

• 记录一个当前以及有多少个连续的 cat ，如果遍历到当前节点， cat 数目 >m ，就不需要继续 dfs 了；
• 然后判断一下是不是叶子节点即可；

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static int res;
    // static int[] in;
    static boolean[] isCat;
    static boolean[] vis;
    static ArrayList<Integer> G[];

    static int calculate() {
        dfs(0, 0);
        return res;
    }

    static void dfs(int v, int curSum) {
        vis[v] = true;
        if (isCat[v])
            curSum += 1;
        if (curSum > m)
            return;
//        if(v != 0 && in[v] == 1) // is leaf and is not root(0)
//            res += 1;
        if (v != 0 && G[v].size() == 1)  // is leaf and is not root(0)
            res += 1;
        else {
            for (int i = 0; i < G[v].size(); i++)
                if (!vis[G[v].get(i)])
                    dfs(G[v].get(i), isCat[v] ? curSum : 0);
        }
    }


    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        n = cin.nextInt();
        m = cin.nextInt();
        G = new ArrayList[n];
        isCat = new boolean[n];
        vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            G[i] = new ArrayList<>();
            vis[i] = false;
        }
        res = 0;
        for (int i = 0; i < n; i++) {
            int num = cin.nextInt();
            isCat[i] = num == 1 ? true : false;
        }
        for (int i = 0; i < n - 1; i++) {
            int from = cin.nextInt();
            int to = cin.nextInt();
            G[from - 1].add(to - 1);
            G[to - 1].add(from - 1);
        }
        out.println(calculate());
    }
}

题目链接

https://codeforces.com/contest/580/problem/C