Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define e1 first
- #define e2 second
- #define pb push_back
- #define mp make_pair
- #define boost ios_base::sync_with_stdio(false)
- #define eb emplace_back
- #define OUT(x) {cout << x; exit(0); }
- #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
- #define scanf(...) scanf(__VA_ARGS__)?:0
- typedef long long int ll;
- typedef unsigned long long ull;
- typedef pair <int, int> PII;
- typedef pair <ll, ll> PLL;
- typedef pair <PLL, int> PLLI;
- typedef pair <PLL, PLL> PP;
- typedef pair <PII, int> PPI;
- typedef pair <ll, int> PLI;
- typedef unsigned int ui;
- const int inf = 1e9+9;
- const ll MOD = 1e9+696969;
- const long long INF = 1e18+3;
- #define maxn 1001000
- vector <int> v[maxn];
- int parent[maxn], n, root, goal, a ,b, d[maxn];
- bool onpath[maxn];
- int POST[maxn], VER;
- void countEverything(int x, int par)
- {
- parent[x] = par;
- for (auto u : v[x])
- if (u != par)
- {
- d[u] = d[x] + 1;
- countEverything(u, x);
- }
- POST[++VER] = x;
- }
- int cost[maxn];
- inline int deg(int x) {
- return (int)v[x].size();
- }
- int sciezka[maxn], DS;
- void dfs(int x, int par) {
- //cout << "Where am i: " << x << endl;
- for (auto u : v[x])
- if (!onpath[u] && u != par)
- {
- cost[u] = cost[x] + deg(u) - 1;
- dfs(u, x);
- }
- }
- bool zle[maxn];
- int dp[maxn];
- bool check(int k)
- {
- FOR(i, 1, n) dp[i] = 0;
- FOR(i, 1, n)
- {
- int x = POST[i];
- dp[x]--;
- if (cost[x] > k) dp[x] = 1;
- else dp[x] = max(0, dp[x]);
- dp[x] = min(dp[x], 1);
- if (x != root) dp[parent[x]] += dp[x];
- }
- return (dp[root] == 0);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n >> goal >> root;
- assert(goal <= n); assert(root <= n);
- if (goal == root) OUT(0);
- FOR(i, 2, n)
- {
- cin >> a >> b;
- v[a].pb(b);
- v[b].pb(a);
- }
- countEverything(root, root);
- int x = goal, y = 0;
- while (x != root)
- {
- onpath[x] = 1;
- sciezka[++DS] = x;
- x = parent[x];
- }
- onpath[root] = 1;
- sciezka[++DS] = x;
- int pathOnly = 0;
- pathOnly -= (d[goal] - 1);
- FOR(i, 1, DS)
- {
- int u = sciezka[i];
- if (u != goal) pathOnly += deg(sciezka[i]) - 1;
- if (u != goal) dfs(u, u);
- }
- x = 0, y = n + n;
- while (x < y)
- {
- int sr = (x + y) >> 1;
- if (!check(sr)) x = ++sr;
- else y = sr;
- }
- cout << pathOnly + x;
- }
Advertisement
Add Comment
Please, Sign In to add comment