// by szh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}
const int maxn = 1010;
int n;
vector <int> edge[maxn];
int cnt = 0;
int x, y;
int dp[maxn];
int ans = 0;
int solve(int u, int fa) {
vector <int> val;
for (auto v : edge[u]) {
if (v == fa) continue;
solve(v, u);
val.pb(dp[v]);
}
sort(ALL(val));
reverse(ALL(val));
rep(i, 0, SZ(val)) dp[u] = max(dp[u], val[i] + i + 1);
return dp[u];
}
vector <int> node;
bool dfs(int u, int fa) {
if (u == y) node.pb(u);
if (u == y) return true;
for (int v : edge[u]) {
if (v == fa) continue;
if (dfs(v, u)) {
node.pb(u);
return true;
}
}
return false;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> x >> y;
rep(i, 1, n) {
int u, v;
cin >> u >> v;
edge[u].pb(v);
edge[v].pb(u);
}
dfs(x, -1);
if (SZ(node) == 2) {
ans = max(solve(x, y), solve(y, x));
cout << ans;
return 0;
}
ans = max(solve(node[0], node[1]), solve(node.back(), node[SZ(node)-2]));
debug(ans);
int lcur = 0, lcnt = SZ(edge[node[0]]) - 1;
int rcur = SZ(node) - 1, rcnt = SZ(edge[node.back()]) - 1;
while (1) {
if (lcnt < rcnt) {
lcur++;
lcnt += SZ(edge[node[lcur]]) - 1;
}
else {
rcur--;
rcnt += SZ(edge[node[rcur]]) - 1;
}
if (lcur == rcur) break;
}
int tmp = 0;
rep(i, 1, lcur) {
tmp++;
int u = node[i];
vector <int> val;
for (int v:edge[u]) {
if (v == node[i-1] or v == node[i+1]) continue;
dfs(v, u);
val.pb(dp[v]);
}
sort(ALL(val));
reverse(ALL(val));
for (auto it:val) tmp++, ans = max(ans, tmp + it);
}
debug(ans);
tmp = 0;
for (int i = SZ(node) - 2; i > rcur; i--) {
tmp++;
int u = node[i];
vector <int> val;
for (int v:edge[u]) {
if (v == node[i-1] or v == node[i+1]) continue;
dfs(v, u);
val.pb(dp[v]);
}
sort(ALL(val));
reverse(ALL(val));
for (auto it:val) tmp++, ans = max(ans, tmp + it);
}
int u = node[lcur];
vector <int> val;
for (int v:edge[u]) {
if (v == node[lcur-1] or v == node[rcur+1]) continue;
dfs(v, u);
val.pb(dp[v]);
}
debug(ans);
debug(lcur);
lcnt++, rcnt++;
lcnt -= SZ(edge[node[lcur]]) - 1;
rcnt -= SZ(edge[node[lcur]]) - 1;
debug(lcnt), debug(rcnt);
for (auto it : val) {
if (lcnt < rcnt) {
lcnt++;
ans = max(ans, lcnt + it);
}
else {
rcnt++;
ans = max(ans, rcnt + it);
}
}
debug(dp[3]);
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
