[Spoj] HOLI - Holiday Accommodation

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : HOLI - Holiday Accommodation
Source            : Spoj
Category          : Graph Theory, Mathematics
Algorithm         : dfs, Pigeonhole Theorem
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2.   
3. using namespace std;  
4.   
5. #define ll              long long int  
6.   
7. static const int maxn = 1e5 + 5;  
8.   
9. struct node  
10. {  
11.       int v;  
12.       ll w;  
13.       node(int v = 0, ll w = 0) : v(v), w(w) {}  
14. };  
15.   
16. int tnode;  
17. vector <node> graph[maxn];  
18. int subtreeSize[maxn];  
19.   
20. inline void dfs(int u = 1, int p = -1)  
21. {  
22.       subtreeSize[u] = 1;  
23.       for (node g : graph[u])  
24.       {  
25.             if (g.v == p) continue;  
26.             dfs(g.v, u);  
27.             subtreeSize[u] += subtreeSize[g.v];  
28.       }  
29. }  
30.   
31. inline ll getCost(int u = 1, int p = -1)  
32. {  
33.       ll cost = 0;  
34.       for (node g : graph[u])  
35.       {  
36.             if (g.v == p) continue;  
37.             int minSize = min(subtreeSize[g.v], tnode - subtreeSize[g.v]);  
38.             cost += (g.w * minSize) + getCost(g.v, u);  
39.       }  
40.       return cost;  
41. }  
42.   
43. int main()  
44. { 
45.       int tc;  
46.       scanf("%d", &tc);  
47.       for (int tcase = 1; tcase <= tc; tcase++)  
48.       {  
49.             scanf("%d", &tnode);  
50.             for (int e = 1; e < tnode; e++)  
51.             {  
52.                   int u, v;  
53.                   ll w;  
54.                   scanf("%d %d %lld", &u, &v, &w);  
55.                   graph[u].emplace_back(v, w);  
56.                   graph[v].emplace_back(u, w);  
57.             }  
58.             dfs();  
59.             ll ans = getCost();  
60.             printf("Case #%d: %lld\n", tcase, ans * 2);  
61.             for (int i = 1; i <= tnode; i++) graph[i].clear();  
62.       }  
63. }