Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 5e4 + 10;
- array<vector<int>, MAXN> grafo;
- array<int, MAXN> cnt;
- void dfs(int v, int p)
- {
- for (auto viz : grafo[v])
- {
- if (viz == p) continue;
- dfs(viz, v);
- }
- int extra = 1;
- for (int k = 17; k >= 0; k--)
- {
- int marc = 0;
- for (auto viz : grafo[v])
- {
- if (viz == p) continue;
- marc += (((cnt[viz]) >> k)&1);
- }
- if (marc <= 1) continue;
- extra = 0;
- cnt[v] = (1 << (k+1));
- for (auto viz : grafo[v])
- {
- if (viz == p) continue;
- cnt[v] += cnt[viz] - (cnt[viz] % (1 << (k+1)));
- }
- break;
- }
- if (extra == 1) for (auto viz : grafo[v]) if (viz != p) cnt[v] += cnt[viz];
- cnt[v] += extra;
- // cerr << "v: " << v << ", cnt: " << bitset<4>(cnt[v]) << '\n';
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N;
- cin >> N;
- for (int i = 1; i < N; i++)
- {
- int X, Y;
- cin >> X >> Y;
- grafo[X].push_back(Y);
- grafo[Y].push_back(X);
- }
- dfs(1, 1);
- cout << 31 - __builtin_clz(cnt[1]) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
