正文
CodeForces - 580C Kefa and Park 【BFS】
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目链接
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());
}
