Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MX_SZ = 5000 + 42;
- const int MX_H = 14;
- vector<int> g[MX_SZ];
- int tin[MX_SZ], tout[MX_SZ], timer = 1, sz[MX_SZ], h[MX_SZ];
- int pr[MX_SZ][MX_H];
- void dfs_pre(int v, int p, int ch)
- {
- h[v] = ch;
- tin[v] = timer;
- timer++;
- pr[v][0] = p;
- for (int i = 1; i < MX_H; i++)
- {
- pr[v][i] = pr[pr[v][i - 1]][i - 1];
- }
- for (int u : g[v])
- {
- if (u != p)
- {
- dfs_pre(u, v, ch + 1);
- sz[v] += sz[u];
- }
- }
- sz[v]++;
- tout[v] = timer;
- timer++;
- return;
- }
- inline bool upper(int v, int u)
- {
- return tin[v] < tin[u] and tout[v] > tout[u];
- }
- inline int lca(int v, int u)
- {
- for (int i = MX_H - 1; i >= 0; i--)
- {
- if (!upper(pr[v][i], u))
- {
- v= pr[v][i];
- }
- }
- return pr[v][0];
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- for (int i = 0; i < n - 1; i++)
- {
- int x, y;
- cin >> x >> y;
- g[x].push_back(y);
- g[y].push_back(x);
- }
- dfs_pre(1, 1, 1);
- int ans = 0;
- for (int v = 1; v <= n; v++)
- {
- for (int u = v + 1; u <= n; u++)
- {
- int cv = v, cu = u, cu1 = -1;
- int ch, realh;
- bool skip = false;
- if (upper(cv, cu) or upper(cu, cv))
- {
- if (upper(cu, cv))
- {
- swap(cv, cu);
- }
- realh = h[cu] - h[cv];
- ch = (h[cu] - h[cv] - 1) / 2;
- }
- else
- {
- int clca = lca(cv, cu);
- if (h[cv] > h[cu])
- {
- swap(cu, cv);
- }
- realh = h[cv] + h[cu] - 2 * h[clca];
- ch = (realh - 1) / 2;
- if (h[cv] == h[cu])
- {
- skip = true;
- int cnt1 = 0;
- cu1 = cv;
- for (int j = MX_H - 1; j >= 0; j--)
- {
- if (cnt1 + (1 << j) <= ch)
- {
- cnt1 += (1 << j);
- cu1 = pr[cu1][j];
- }
- }
- }
- }
- int cnt = 0;
- for (int j = MX_H - 1; j >= 0; j--)
- {
- if (cnt + (1 << j) <= ch)
- {
- cnt += (1 << j);
- cu = pr[cu][j];
- }
- }
- if (sz[cu] == sz[cu1] and skip)
- {
- ans++;
- }
- if (skip)
- {
- continue;
- }
- if (cu1 == -1)
- {
- cu1 = pr[cu][0];
- }
- if (realh % 2 == 0)
- {
- if (sz[cu] == n - sz[cu1])
- {
- ans++;
- }
- }
- else
- {
- if (sz[cu] == n - sz[cu])
- {
- ans++;
- }
- }
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement