#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 5007;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;
vector <int> adj[M], va, vb;
int n, a, b;
bool ok;
int dfs(int node, int p, int wr){
if(node == wr) return -inf;
vector <int> v;
for(auto i : adj[node]) if(i != p)
v.pb(dfs(i, node, wr));
sort(all(v), greater <int> ());
if(!p){
if(node == a) va = v;
else vb = v;
}
int mx = 0;
for(int i = 0; i < v.size(); ++i) mx = max(mx, v[i] + i);
return mx + 1;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> a >> b;
for(int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
if(x == a && y == b) ok = 1;
if(x == b && y == a) ok = 1;
}
dfs(a, 0, b);
dfs(b, 0, a);
va.pop_back(); vb.pop_back();
for(int i = (int) va.size() - 1; i >= 0; --i){
va[i] += i;
if(i + 1 < va.size()) va[i] = max(va[i], va[i + 1]);
}
for(int i = (int) vb.size() - 1; i >= 0; --i){
vb[i] += i;
if(i + 1 < vb.size()) vb[i] = max(vb[i], vb[i + 1]);
}
int mx = 0;
if(va.size()) mx = max(mx, va[0]);
if(vb.size()) mx = max(mx, vb[0]);
if(ok || (va.size() && va.back() < mx) || (vb.size() && vb.back() < mx) || va.size() != vb.size()) cout << mx << endl;
else cout << mx + 1 << endl;
return 0;
}
Compilation message
torrent.cpp: In function 'int dfs(int, int, int)':
torrent.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i = 0; i < v.size(); ++i) mx = max(mx, v[i] + i);
| ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if(i + 1 < va.size()) va[i] = max(va[i], va[i + 1]);
| ~~~~~~^~~~~~~~~~~
torrent.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(i + 1 < vb.size()) vb[i] = max(vb[i], vb[i + 1]);
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
