Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <map>
- #include <set>
- #include <list>
- #include <cmath>
- #include <ctime>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <string>
- #include <bitset>
- #include <cstdio>
- #include <limits>
- #include <vector>
- #include <climits>
- #include <cstring>
- #include <cstdlib>
- #include <fstream>
- #include <numeric>
- #include <sstream>
- #include <cassert>
- #include <iomanip>
- #include <iostream>
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- #define pii pair<int, int>
- using namespace std;
- const int N = (int) 2e5 + 10;
- const int MOD = (int) 1e9 + 7;
- int n;
- vector<int> g[N];
- int dp[N];
- int up[N];
- int batya[N];
- int combine(int a, int b) {
- if (a == 0 || b == 0)
- return a ? a : b;
- if (a == -1 || b == -1 || a != b)
- return -1;
- assert(a == b);
- return a;
- }
- void dfs(int v, int parent = 0) {
- batya[v] = parent;
- for (auto to : g[v]) {
- if (to == parent) continue;
- dfs(to, v);
- dp[v] = combine(dp[v], dp[to]);
- }
- if (dp[v] != -1) ++dp[v];
- }
- void calc_up(int v, int parent = 0) {
- vector<int> children;
- for (auto to : g[v]) {
- if (to == parent) continue;
- children.pb(to);
- }
- if (children.empty())
- return;
- vector<int> prefix;
- prefix.resize(children.size());
- for (int i = 0; i < prefix.size(); i++) {
- if (i) prefix[i] = prefix[i - 1];
- prefix[i] = combine(prefix[i], dp[children[i]]);
- }
- int suffix = 0;
- for (int i = (int) children.size() - 1; i >= 0; i--) {
- int to = children[i];
- int we = combine(suffix, i ? prefix[i - 1] : 0);
- up[to] = combine(we, up[v]);
- if (up[to] != -1) up[to]++;
- calc_up(to, v);
- suffix = combine(suffix, dp[children[i]]);
- }
- }
- int main() {
- #ifdef LOCAL
- freopen("in.txt", "r", stdin);
- //freopen("out", "w", stdout);
- #endif
- scanf("%d", &n);
- for (int i = 1; i < n; i++) {
- int u, v;
- scanf("%d%d", &u, &v);
- g[u].pb(v);
- g[v].pb(u);
- }
- dfs(1);
- calc_up(1);
- //for (int i = 1; i <= n; i++)
- // cout << dp[i] << ' ';
- //cout << endl;
- //for (int i = 1; i <= n; i++)
- // cout << up[i] << ' ';
- //cout << endl;
- //for (int i = 1; i <= n; i++)
- // if (up[i] != -1) --up[i];
- int ans = MOD;
- for (int root = 1; root <= n; root++) {
- vector<int> deti;
- for (auto to : g[root]) {
- if (to == batya[root]) continue;
- deti.pb(dp[to]);
- }
- if (up[root])
- deti.pb(up[root]);
- sort(deti.begin(), deti.end());
- deti.resize(unique(deti.begin(), deti.end()) - deti.begin());
- if (deti.size() > 2) continue;
- if (deti.empty()) continue;
- if (deti[0] == -1) continue;
- int sum = 0;
- for (auto it : deti) sum += it;
- ans = min(ans, sum);
- }
- if (ans == MOD) {
- cout << -1;
- return 0;
- }
- while (ans % 2 == 0) ans /= 2;
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment