Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define MAXN 300010
- int N, a, b;
- vector< int >colleg[MAXN];
- bool visited[MAXN];
- int scelta[MAXN];
- int Dfs(int n, int verso) {
- visited[n]=true;
- if(n == verso) return scelta[n] = n;
- for(int i : colleg[n]) {
- if(visited[i]) continue;
- int tmp = Dfs(i, verso);
- if(tmp > -1) { scelta[n] = i; break; }
- }
- return scelta[n];
- }
- int Colora(int rad, pair<int, int>bloccato) {
- visited[rad]=true;
- vector< int >cosi;
- for(int i : colleg[rad]) {
- if( (make_pair(rad, i) ==bloccato) || (make_pair(i, rad)==bloccato) ) continue;
- if(visited[i]) continue;
- cosi.push_back(1 + Colora(i, bloccato));
- }
- sort(cosi.begin(), cosi.end());
- reverse(cosi.begin(), cosi.end());
- int ris=0;
- for(int i=0;i<(int)cosi.size();i++) ris=max(ris, i + cosi[i]);
- return ris;
- }
- pair<int, int> Controlla(pair<int, int>arco) {
- memset(visited, false, sizeof visited);
- int ans1 = Colora(a, arco);
- memset(visited, false, sizeof visited);
- int ans2 = Colora(b, arco);
- return {ans1, ans2};
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> N >> a >> b;
- int p, q;
- for(int i=0;i<N-1;i++) {
- cin>>p>>q;
- colleg[p].push_back(q);
- colleg[q].push_back(p);
- }
- memset(scelta, -1, sizeof scelta);
- Dfs(a, b);
- vector< pair<int, int> >v;
- int parto = a;
- while(parto != b) v.push_back({parto, scelta[parto]}), parto=scelta[parto];
- int ris = -1;
- int low=0, high=(int)v.size() - 1, mid=0;
- while(low <= high) {
- mid= (low+high)/2;
- pair<int, int> tmp_ans = Controlla(v[mid]);
- int tmp_a = tmp_ans.first, tmp_b = tmp_ans.second;
- pair<int, int> avanti = ((mid+1 >= (int)v.size()) ? make_pair(-1,-1) : Controlla(v[mid+1]));
- ris=(ris==-1) ? max(tmp_a, tmp_b) : min(ris, max(tmp_a, tmp_b));
- if(avanti.first==-1) break;
- if(max(tmp_a, tmp_b) > max(avanti.first, avanti.second)) low=mid+1;
- else if(max(tmp_a, tmp_b) > max(avanti.first, avanti.second)) high=mid-1;
- else {
- if(tmp_a < tmp_b) low=mid+1;
- else high=mid-1;
- /* if(tmp_a <= tmp_b) low=mid+1;
- * else high=mid-1;
- */
- }
- }
- cout << ris << endl;
- return EXIT_SUCCESS;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement