LA 3902 网络

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 1000 + 10;
 6 
 7 int n,s,k;
 8 vector<int> gr[maxn],nodes[maxn];
 9 
10 
11 int fa[maxn];
12 void dfs(int u,int f,int d)
13 {
14     fa[u] = f;
15     int nc = gr[u].size();
16     if(nc==1&&d>k) nodes[d].push_back(u);
17     for(int i=0; i<nc; i++)
18     {
19         int v = gr[u][i];
20         if(v!=f)
21             dfs(v,u,d+1);
22     }
23 }
24 
25 
26 bool covered[maxn];
27 
28 void dfs2(int u,int f,int d)
29 {
30     covered[u] = true;
31     int nc = gr[u].size();
32     for(int i=0; i<nc; i++)
33     {
34         int v = gr[u][i];
35         if(v!=f&&d<k)
36             dfs2(v,u,d+1);
37     }
38 }
39 
40 int solve()
41 {
42     int ans = 0;
43     memset(covered,0,sizeof(covered));
44     for(int d=n-1; d>k; d--)
45     {
46         for(int i=0; i<nodes[d].size(); i++)
47         {
48             int u = nodes[d][i];
49             if(covered[u])
50                 continue;
51 
52             int v = u;
53             for(int j=0; j<k; j++)
54                 v = fa[v];
55             dfs2(v,-1,0);
56             ans++;
57         }
58     }
59     return ans;
60 }
61 
62 int main()
63 {
64     int t;
65     scanf("%d",&t);
66     while(t--)
67     {
68         scanf("%d%d%d",&n,&s,&k);
69         for(int i=1; i<=n; i++)
70         {
71             gr[i].clear();
72             nodes[i].clear();
73         }
74 
75         for(int i=0; i<n-1; i++)
76         {
77             int a,b;
78             scanf("%d%d",&a,&b);
79             gr[a].push_back(b);
80             gr[b].push_back(a);
81         }
82 
83         dfs(s,-1,0);
84         printf("%d\n",solve());
85     }
86 
87     return 0;
88 }