Na2a

Untitled

Feb 14th, 2017
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <map>
  2. #include <set>
  3. #include <list>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <string>
  10. #include <bitset>
  11. #include <cstdio>
  12. #include <limits>
  13. #include <vector>
  14. #include <climits>
  15. #include <cstring>
  16. #include <cstdlib>
  17. #include <fstream>
  18. #include <numeric>
  19. #include <sstream>
  20. #include <cassert>
  21. #include <iomanip>
  22. #include <iostream>
  23. #include <algorithm>
  24. #include <unordered_set>
  25. #include <unordered_map>
  26.  
  27. #define pb push_back
  28. #define mp make_pair
  29.  
  30. #define f first
  31. #define s second
  32.  
  33. #define pii pair<int, int>
  34.  
  35. using namespace std;
  36.  
  37. const int N = (int) 2e5 + 10;
  38. const int MOD = (int) 1e9 + 7;
  39.  
  40. int n;
  41. vector<int> g[N];
  42.  
  43. int dp[N];
  44. int up[N];
  45. int batya[N];
  46.  
  47. int combine(int a, int b) {
  48.   if (a == 0 || b == 0)
  49.     return a ? a : b;
  50.   if (a == -1 || b == -1 || a != b)
  51.     return -1;
  52.   assert(a == b);
  53.   return a;
  54. }
  55.  
  56. void dfs(int v, int parent = 0) {
  57.   batya[v] = parent;
  58.   for (auto to : g[v]) {
  59.     if (to == parent) continue;
  60.     dfs(to, v);
  61.     dp[v] = combine(dp[v], dp[to]);
  62.   }
  63.   if (dp[v] != -1) ++dp[v];
  64. }
  65.  
  66. void calc_up(int v, int parent = 0) {
  67.   vector<int> children;
  68.   for (auto to : g[v]) {
  69.     if (to == parent) continue;
  70.     children.pb(to);
  71.   }
  72.   if (children.empty())
  73.     return;
  74.   vector<int> prefix;
  75.   prefix.resize(children.size());
  76.   for (int i = 0; i < prefix.size(); i++) {
  77.     if (i) prefix[i] = prefix[i - 1];
  78.     prefix[i] = combine(prefix[i], dp[children[i]]);
  79.   }
  80.   int suffix = 0;
  81.   for (int i = (int) children.size() - 1; i >= 0; i--) {
  82.     int to = children[i];
  83.     int we = combine(suffix, i ? prefix[i - 1] : 0);
  84.     up[to] = combine(we, up[v]);
  85.     if (up[to] != -1) up[to]++;
  86.     calc_up(to, v);
  87.     suffix = combine(suffix, dp[children[i]]);
  88.   }
  89. }
  90.  
  91. int main() {
  92.   #ifdef LOCAL
  93.   freopen("in.txt", "r", stdin);
  94.   //freopen("out", "w", stdout);
  95.   #endif
  96.  
  97.   scanf("%d", &n);
  98.   for (int i = 1; i < n; i++) {
  99.     int u, v;
  100.     scanf("%d%d", &u, &v);
  101.     g[u].pb(v);
  102.     g[v].pb(u);
  103.   }
  104.   dfs(1);
  105.   calc_up(1);
  106.   //for (int i = 1; i <= n; i++)
  107.   //  cout << dp[i] << ' ';
  108.   //cout << endl;
  109.   //for (int i = 1; i <= n; i++)
  110.   //  cout << up[i] << ' ';
  111.   //cout << endl;
  112.   //for (int i = 1; i <= n; i++)
  113.   //  if (up[i] != -1) --up[i];
  114.   int ans = MOD;
  115.   for (int root = 1; root <= n; root++) {
  116.     vector<int> deti;
  117.     for (auto to : g[root]) {
  118.       if (to == batya[root]) continue;
  119.       deti.pb(dp[to]);
  120.     }
  121.     if (up[root])
  122.       deti.pb(up[root]);
  123.     sort(deti.begin(), deti.end());
  124.     deti.resize(unique(deti.begin(), deti.end()) - deti.begin());
  125.     if (deti.size() > 2) continue;
  126.     if (deti.empty()) continue;
  127.     if (deti[0] == -1) continue;
  128.     int sum = 0;
  129.     for (auto it : deti) sum += it;
  130.     ans = min(ans, sum);
  131.   }
  132.   if (ans == MOD) {
  133.     cout << -1;
  134.     return 0;
  135.   }
  136.   while (ans % 2 == 0) ans /= 2;
  137.   cout << ans;
  138.   return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment