Work

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

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

解题：一顿乱搞

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 struct arc {

     int to,next;

     arc(int x = ,int y = -) {

         to = x;

         next = y;

     }

 } e[maxn];

 int head[maxn],tot;

 void add(int u,int v) {

     e[tot] = arc(v,head[u]);

     head[u] = tot++;

     e[tot] = arc(u,head[v]);

     head[v] = tot++;

 }

 int ind[maxn],cnt[maxn],ret,n,k;

 void dfs(int u,int fa) {

     cnt[u] = ;

     for(int i = head[u]; ~i; i = e[i].next) {

         if(e[i].to == fa) continue;

         dfs(e[i].to,u);

         cnt[u] += cnt[e[i].to];

     }

     if(k +  == cnt[u]) ++ret;

 }

 int main() {

     int u,v;

     while(~scanf("%d%d",&n,&k)) {

         memset(head,-,sizeof head);

         memset(ind,,sizeof ind);

         ret = tot = ;

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

             scanf("%d%d",&u,&v);

             add(u,v);

             ++ind[v];

         }

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

             if(!ind[i]) {

                 dfs(i,-);

                 break;

             }

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

     }

     return ;

 }

巴特西

2015 Multi-University Training Contest 3 hdu 5326 Work

Work

最新文章

热门文章