多校3 1011 Work

Work

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 230 Accepted Submission(s): 171

Problem Description

It’s an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company.
As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A’s title is higher than B(A is the direct or indirect leader of B), we call it A manages B.
Now, give you the relation of a company, can you calculate how many people manage k people.

Input

There are multiple test cases.
Each test case begins with two integers n and k, n indicates the number of stuff of the company.
Each of the following n-1 lines has two integers A and B, means A is the direct leader of B.

1 <= n <= 100 , 0 <= k < n
1 <= A, B <= n

Output

For each test case, output the answer as described above.

Sample Input

7 2 1 2 1 3 2 4 2 5 3 6 3 7

Sample Output

Source

2015 Multi-University Training Contest 3

Recommend

wange2014 | We have carefully selected several similar problems for you: 5326 5325 5324 5323 5322

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int n,k,s;
 7 int a[105][105];
 8 
 9 int dfs(int g)
10 {
11     for(int i=1;i<=n;i++)
12     {
13         if(a[g][i]==1)
14         {
15             s++;
16             dfs(i);
17         }
18     }
19     return 0;
20 }
21 
22 int main()
23 {
24     int i,j,x,y;
25     while(scanf("%d %d",&n,&k)!=EOF)
26     {
27         memset(a,0,sizeof(a));
28         for(i=1;i<=n-1;i++)
29         {
30             scanf("%d %d",&x,&y);
31             a[x][y]=1;
32         }
33         int ans=0;
34         for(i=1;i<=n;i++)
35         {
36             s=0;
37             dfs(i);
38             if(s==k)
39                 ans++;
40         }
41         printf("%d
",ans);
42     }
43 }

View Code