#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> v[300005];
vector <int> v1;
int cnt[2][300005];
bool sort_function1(int a,int b) {
return cnt[0][a]>cnt[0][b];
}
bool sort_function2(int a,int b) {
return cnt[1][a]>cnt[1][b];
}
int dfs(int x,int par,int c) {
if(x==c) return 1;
int ret=0;
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
if(dfs(v[x][i],x,c)) {
ret+=1;
v1.push_back(v[x][i]);
}
}
return ret;
}
int f(int x,int par,int ind) {
//cout << x << " " << ind << "\n";
int ret=1;
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
ret+=f(v[x][i],x,ind);
}
cnt[ind][x]=ret;
return ret;
}
int eval(int x,int par,int ind) {
//cout << x << "\n";
int ret=0,y=0;
if(ind) sort(v[x].begin(),v[x].end(),sort_function2);
else sort(v[x].begin(),v[x].end(),sort_function1);
for(int i=0;i<v[x].size();i++) {
if(v[x][i]==par) continue;
//cout << v[x][i] << " " << cnt[ind][v[x][i]] << "\n";
ret=max(ret,eval(v[x][i],x,ind)+1+y);
y+=1;
}
//cout << x << " " << ret << "\n";
//cout << "\n\n";
return ret;
}
int main()
{
int n,a,b,sol=0;
cin >> n >> a >> b;
a-=1;
b-=1;
for(int i=0;i<n-1;i++) {
int x,y;
cin >> x >> y;
v[x-1].push_back(y-1);
v[y-1].push_back(x-1);
}
f(a,-1,0);
f(b,-1,1);
dfs(a,-1,b);
v1.push_back(a);
reverse(v1.begin(),v1.end());
int lo=1,hi=v1.size()-1;
/*cout << "\n";
for(int i=0;i<n;i++) {
cout << i+1 << " " << cnt[1][i] << "\n";
}
cout << "\n";*/
if(lo>=hi) {
v[a].erase(find(v[a].begin(),v[a].end(),b));
v[b].erase(find(v[b].begin(),v[b].end(),a));
cout << max(eval(a,-1,0),eval(b,-1,1));
//cout << eval(a,-1,0) << " " << eval(b,-1,1) << "\n";
return 0;
}
while(lo<hi) {
int mid=(lo+hi)/2;
if(hi-lo==1) mid=hi;
if(mid>0 && mid<v1.size()) {
v[v1[mid-1]].erase(find(v[v1[mid-1]].begin(),v[v1[mid-1]].end(),v1[mid]));
v[v1[mid]].erase(find(v[v1[mid]].begin(),v[v1[mid]].end(),v1[mid-1]));
}
//cout << mid << " " << eval(a,-1,0) << " " << eval(b,-1,1) << "\n";
if(eval(a,-1,0)>eval(b,-1,1)) {
lo=mid;
sol=eval(a,-1,0);
}
else {
hi=mid-1;
sol=eval(b,-1,1);
}
}
cout << sol;
return 0;
}
Compilation message
torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
torrent.cpp: In function 'int f(int, int, int)':
torrent.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
torrent.cpp: In function 'int eval(int, int, int)':
torrent.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++) {
~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mid>0 && mid<v1.size()) {
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
925 ms |
26440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
