[toph.co] Darth Vader and 3PO on a Tree!

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Darth Vader and 3PO on a Tree! 
Source            : toph.co
Category          : Graph Theory, Dynamic Programing
Algorithm         : DP on Tree, In Out DP
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2.   
3. using namespace std;  
4.   
5. #define inf                                   12345678  
6.   
7. static const int maxn = 1e5 + 5;  
8.   
9. vector <int> graph[maxn];  
10. int IN[maxn], OUT[maxn], dp[maxn], degree[maxn], root;  
11.   
12. inline void dfs1(int u = 1, int p = -1)  
13. {  
14.       IN[u] = inf;  
15.       for (int v : graph[u])  
16.       {  
17.             if (v == p) continue;  
18.             dfs1(v, u);  
19.             IN[u] = min(IN[u], 1 + IN[v]);  
20.       }  
21.       if (degree[u] == 1 && u != 1) IN[u] = 0;  
22. }  
23.   
24. inline void dfs2(int u = 1, int p = -1)  
25. {  
26.       int min1 = inf;  
27.       int min2 = inf;  
28.       for (int v : graph[u])  
29.       {  
30.             if (v == p) continue;  
31.             if (IN[v] <= min1)  
32.             {  
33.                   min2 = min1;  
34.                   min1 = IN[v];  
35.             }  
36.             else if (IN[v] < min2)  
37.             {  
38.                   min2 = IN[v];  
39.             }  
40.       }  
41.       for (int v : graph[u])  
42.       {  
43.             if (v == p) continue;  
44.             int use = min1;  
45.             if (IN[v] == use) use = min2;  
46.             OUT[v] = min(1 + OUT[u], 2 + use);  
47.             dfs2(v, u);  
48.       }  
49. }  
50.   
51.   
52. int main(int argc, char const *argv[])  
53. {  
54.       //freopen("in.txt", "r", stdin);  
55.       int tnode;  
56.       scanf("%d", &tnode);  
57.       for (int i = 1; i < tnode; i++)  
58.       {  
59.             int u, v;  
60.             scanf("%d %d", &u, &v);  
61.             degree[u]++;  
62.             degree[v]++;  
63.             graph[u].push_back(v);  
64.             graph[v].push_back(u);  
65.       }  
66.       dfs1();  
67.       memset(OUT, inf, sizeof OUT);  
68.       if (degree[1] == 1) OUT[1] = 0;  
69.       dfs2();  
70.       for (int i = 1; i <= tnode; i++)  
71.       {  
72.             dp[i] = min(IN[i], OUT[i]);  
73.       }  
74.       sort(dp + 1, dp + tnode + 1);  
75.       int sum_3PO = 0;  
76.       int sum_Darth_Vade = 0;  
77.       for (int i = 1; i <= tnode; i++)  
78.       {  
79.             if (i & 1) sum_3PO += dp[i];  
80.             else sum_Darth_Vade += dp[i];  
81.       }  
82.       if (sum_3PO < sum_Darth_Vade) puts("3PO");  
83.       else if (sum_3PO > sum_Darth_Vade) puts("Darth Vader");  
84.       else puts("Draw");  
85. }