[UVa] 13274 - Christmas Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13274 - Christmas Tree
Source            : UVA Online Judge
Category          : Graph Theory, Dynamic Programing
Algorithm         : DP on Tree
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. static const int maxn = 1e3 + 5;  
6. static const int logn = 15;  
7.   
8. struct node  
9. {  
10.       int name, totalNode;  
11.       node() {}  
12.       node(int _name, int _totalNode)  
13.       {  
14.             name = _name;  
15.             totalNode = _totalNode;  
16.       }  
17.       inline friend bool operator<(node A, node B)  
18.       {  
19.             return A.totalNode > B.totalNode;  
20.       }  
21. };  
22.   
23. vector <int> graph[maxn];  
24. int total_node[maxn], ok[maxn], discover[maxn], dfsTime,  
25.     tnode, k, tnode_beautiful_tree;  
26.   
27. inline void initialize()  
28. {  
29.       dfsTime = 0;  
30.       for (int i = 0; i < maxn; i++)  
31.       {  
32.             graph[i].clear();  
33.             total_node[i] = 0;  
34.             ok[i] = 0;  
35.             discover[i] = 0;  
36.             tnode_beautiful_tree = 0;  
37.     }  
38. }  
39.   
40. inline void dfs(int u = 1, int p = -1)  
41. {  
42.       discover[u] = dfsTime++;  
43.       for (int v : graph[u])  
44.       {  
45.             if (v == p) continue;  
46.             dfs(v, u);  
47.     }  
48. }  
49.   
50. inline void dfs2(int u = 1, int p = -1)  
51. {  
52.       vector <int> vec;  
53.       for (int v : graph[u])  
54.       {  
55.             if (v == p) continue;  
56.             vec.push_back(v);  
57.             dfs2(v, u);  
58.       }  
59.       int sz = vec.size();  
60.       if (sz == 0)  
61.       {  
62.             ok[u] = 1;  
63.             total_node[u] = 1;  
64.       }  
65.       else  
66.       {  
67.             vector <node> vec2;  
68.             ok[u] = 1;  
69.             for (int w : graph[u])  
70.             {  
71.                   if (ok[w] && discover[u] < discover[w])  
72.                   {  
73.                         vec2.push_back({w, total_node[w]});  
74.                   }  
75.             }  
76.             sort(vec2.begin(), vec2.end());  
77.             int len = vec2.size();  
78.             if (len < k)  
79.             {  
80.                   for (node it : vec2)  
81.                   {  
82.                         ok[it.name] = 0;  
83.                   }  
84.             }  
85.             else if (len >= k)  
86.             {  
87.                   int tNum = 0;  
88.                   for (int i = 0; i < k; i++)  
89.                   {  
90.                         tNum += vec2[i].totalNode;  
91.                   }  
92.                   for (int i = k; i < len; i++)  
93.                   {  
94.                         ok[vec2[i].name] = 0;  
95.                   }  
96.                   total_node[u] = tNum + 1;  
97.             }  
98.             vec2.clear();  
99.       }  
100. }  
101.   
102. inline void dfs3(int u = 1, int p = -1)  
103. {  
104.       tnode_beautiful_tree++;  
105.       for (int v : graph[u])  
106.       {  
107.             if (!ok[v] || v == p) continue;  
108.             dfs3(v, u);  
109.       }  
110. }  
111.   
112. int main()  
113. {  
114.       int tc;  
115.       cin >> tc;  
116.       for (int tcase = 1; tcase <= tc; tcase++)  
117.       {  
118.             initialize();  
119.             cin >> tnode >> k;  
120.             for (int i = 1; i < tnode; i++)  
121.             {  
122.                   int u, v;  
123.                   cin >> u >> v;  
124.                   graph[u].push_back(v);  
125.                   graph[v].push_back(u);  
126.             }  
127.             dfs();  
128.             dfs2();  
129.             dfs3();  
130.             cout << "Case " << tcase << ": " << tnode_beautiful_tree << endl;  
131.       }  
132. }  
133.   
134.   
135. /*********************************************** 
136. 1 
137. 16 2 
138. 1 2 
139. 1 3 
140. 1 4 
141. 2 15 
142. 2 16 
143. 3 5 
144. 3 6 
145. 4 8 
146. 4 7 
147. 5 9 
148. 5 10 
149. 6 11 
150. 6 12 
151. 7 13 
152. 7 14 
153.  
154. Case 1: 13 
155.  
156. **********************************************/