题目链接

http://codeforces.com/problemset/problem/580/C

题意

根节点是 1

然后所有的叶子结点都是饭店

从根节点到叶子结点的路径上 如果存在 大于m 个 连续的结点都有猫 那么这条路径就是不可行的

求 最后能到达几个饭店

思路

BFS 就可以了 一层一层往下搜

但是要注意

这个输入的时候

xi yi 没有说 那个是父节点 哪个是儿子结点

那就都给它进去

也就是说 每个结点存的结点里面 有一个结点是自己的父亲结点 用visit[] 访问标记一下就可以了

AC代码

//#include <cstdio>

//#include <cstring>

//#include <ctype.h>

//#include <cstdlib>

//#include <cmath>

//#include <climits>

//#include <ctime>

//#include <iostream>

//#include <algorithm>

//#include <deque>

//#include <vector>

//#include <queue>

//#include <string>

//#include <map>

//#include <stack>

//#include <set>

//#include <list>

//#include <numeric>

//#include <sstream>

//#include <iomanip>

//#include <limits>

//

//#define CLR(a, b) memset(a, (b), sizeof(a))

//#define pb push_back

//#define bug puts("***bug***");

//#define fi first

//#define se second

//#define stack_expand #pragma comment(linker, "/STACK:102400000,102400000")

////#define bug

////#define gets gets_s

//

//using namespace std;

//typedef long long ll;

//typedef long double ld;

//typedef unsigned long long ull;

//typedef pair <int, int> pii;

//typedef pair <ll, ll> pll;

//typedef pair <string, int> psi;

//typedef pair <string, string> pss;

//typedef pair <double, int> pdi;

//

//const double PI = acos(-1.0);

//const double E = exp(1.0);

//const double eps = 1e-8;

//

//const int INF = 0x3f3f3f3f;

//const int maxn = 4e4 + 1e3 + 10;

//const int MOD = 142857;

//

//int index[8] = { 4, 5, 6, 7, 3, 2, 1, 0 };

//

//int visit[maxn];

//

//const int FAC[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

//

//int cantor(int b[8])

//{

//  int ans = 0;

//  for (int i = 0; i < 8; i++)

//  {

//      int smaller = 0;

//      for (int j = i + 1; j < 8; j++)

//      {

//          if (b[i] > b[j])

//              smaller++;

//      }

//      ans += FAC[7 - i] * smaller;

//  }

//  return ans;

//}

//

//struct node

//{

//  int num[8];

//  vector <int> ans;

//};

//

//node st;

//

//int End;

//

//vector <int> ans;

//

//void bfs()

//{

//  queue <node> q;

//  st.ans.clear();

//  q.push(st);

//  int flag = cantor(st.num);

//  if (flag == End)

//      return;

//  visit[flag] = 1;

//  while (!q.empty())

//  {

//      node u = q.front(), v;

//      q.pop();

//

//      // A

//      int i, j;

//      v.num[0] = u.num[7];

//      v.num[1] = u.num[6];

//      v.num[2] = u.num[5];

//      v.num[3] = u.num[4];

//      v.num[4] = u.num[3];

//      v.num[5] = u.num[2];

//      v.num[6] = u.num[1];

//      v.num[7] = u.num[0];

//      v.ans = u.ans;

//      flag = cantor(v.num);

//      if (visit[flag] == 0)

//      {

//          visit[flag] = 1;

//          v.ans.pb(1);

//          q.push(v);

//          if (flag == End)

//          {

//              ans = v.ans;

//              return;

//          }

//      }

//

//      // B

//      v.num[0] = u.num[3];

//      v.num[1] = u.num[0];

//      v.num[2] = u.num[1];

//      v.num[3] = u.num[2];

//      v.num[4] = u.num[5];

//      v.num[5] = u.num[6];

//      v.num[6] = u.num[7];

//      v.num[7] = u.num[4];

//      v.ans = u.ans;

//      flag = cantor(v.num);

//      if (visit[flag] == 0)

//      {

//          visit[flag] = 1;

//          v.ans.pb(2);

//          q.push(v);

//          if (flag == End)

//          {

//              ans = v.ans;

//              return;

//          }

//      }

//

//      // C

//

//      v.num[0] = u.num[0];

//      v.num[1] = u.num[6];

//      v.num[2] = u.num[1];

//      v.num[3] = u.num[3];

//      v.num[4] = u.num[4];

//      v.num[5] = u.num[2];

//      v.num[6] = u.num[5];

//      v.num[7] = u.num[7];

//      //for (int i = 0; i < 8; i++)

//      //  cout << v.num[i];

//      //cout << endl;

//      //getchar();

//      //getchar();

//      v.ans = u.ans;

//      flag = cantor(v.num);

//      if (visit[flag] == 0)

//      {

//          visit[flag] = 1;

//          v.ans.pb(3);

//          q.push(v);

//          if (flag == End)

//          {

//              ans = v.ans;

//              return;

//          }

//      }

//  }

//}

//

//void clear()

//{

//  for (int i = 0; i < maxn; i++)

//      visit[i] = 0;

//  ans.clear();

//}

//

//int main()

//{

//  int a, b;

//  ios::sync_with_stdio(false);

//  cin.tie(0);

//  while (cin >> a >> b)

//  {

//      clear();

//      int num = 1;

//      for (int i = 0, j = 7; i < 8; i++, j--, num *= 10)

//          st.num[j] = (a / num) % 10;

//      //for (int i = 0; i < 8; i++)

//      //  printf("%d", st.num[i]);

//      //cout << endl;

//      int temp[8] = { 0 };

//      num = 1;

//      for (int i = 0, j = 7; i < 8; i++, j--, num *= 10)

//          temp[j] = (b / num) % 10;

//      //for (int i = 0; i < 8; i++)

//      //  printf("%d", temp[i]);

//      //cout << endl;

//      End = cantor(temp);

//      bfs();

//      int len = ans.size();

//      if (len == 0)

//          cout << 1 << endl;

//      for (int i = 0; i < len; i++)

//          printf("%c", 'A' + ans[i] - 1);

//      printf("\n");

//  }

//}

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

#define bug puts("***bug***");

#define fi first

#define se second

#define stack_expand #pragma comment(linker, "/STACK:102400000,102400000")

//#define bug

//#define gets gets_s

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair <string, int> psi;

typedef pair <string, string> pss;

typedef pair <double, int> pdi;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 10;

const int MOD = 142857;

int n, m;

int vis[maxn];

int visit[maxn];

vector <int> edge[maxn];

int root;

struct node

{

    int root, temp, tot;

    node() {}

    node(int root, int temp, int tot) : root(root), temp(temp), tot(tot) {}

};

int bfs()

{

    queue <node> q;

    node u;

    u.root = root;

    u.temp = u.tot = vis[root];

    if (u.tot <= m)

        q.push(u);

    int ans = 0;

    visit[1] = 1;

    while (!q.empty())

    {

        node u = q.front(), v;

        q.pop();

        int len = edge[u.root].size();

        if (len == 1 && u.root != 1)

            ans++;

        for (int i = 0; i < len; i++)

        {

            v.root = edge[u.root][i];

            if (visit[v.root] == 0)

            {

                v.temp = u.temp;

                v.tot = u.tot;

                if (vis[v.root] == 0)

                    v.temp = 0;

                else

                {

                    if (vis[u.root])

                        v.temp++;

                    else

                        v.temp = 1;

                    v.tot = max(v.tot, v.temp);

                }

                if (v.tot <= m)

                    q.push(v);

                visit[v.root] = 1;

            }

        }

    }

    return ans;

}

void clear()

{

    for (int i = 1; i <= n; i++)

        edge[i].clear();

}

int main()

{

    scanf("%d%d", &n, &m);

    clear();

    for (int i = 1; i <= n; i++)

        scanf("%d", &vis[i]);

    int x, y;

    for (int i = 1; i <= n - 1; i++)

    {

        scanf("%d%d", &x, &y);

        edge[x].pb(y);

        edge[y].pb(x);

    }

    root = 1;

    printf("%d\n", bfs());

}