#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)
const int MAX_N = (1 << 12);
int N, A, B, E[MAX_N], F[MAX_N], dist[MAX_N], dp[MAX_N][22], val[MAX_N], pl[MAX_N]; bool used[MAX_N], flag = false;
vector<int>X[MAX_N], Z[MAX_N], lis[MAX_N];
void dfs1(int pos, int dep) {
used[pos] = true; dist[pos] = dep;
for (int i = 0; i < X[pos].size(); i++) {
if (used[X[pos][i]] == true) continue;
dp[X[pos][i]][0] = pos;
dfs1(X[pos][i], dep + 1);
}
}
int prevs(int pos, int x) {
for (int i = 21; i >= 0; i--) {
if (x >= (1 << i)) { pos = dp[pos][i]; x -= (1 << i); }
}
return pos;
}
int lca(int u, int v) {
if (dist[u] > dist[v]) swap(u, v);
v = prevs(v, dist[v] - dist[u]);
if (u == v) return u;
for (int i = 21; i >= 0; i--) {
if (dp[u][i] != dp[v][i]) {
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
int ret[MAX_N], root = 0, G = 2;
int dfs2(int pos) {
used[pos] = true;
int bonus = 0; if (pos == root) bonus = 1;
int GG = 2; if (pos == root) GG = G;
if (flag == false || pos != root) {
if ((int)Z[pos].size() + bonus <= GG) {
return max(1, (int)Z[pos].size() + bonus) - 1;
}
}
else if (Z[pos].size() + bonus <= 1) return 0;
vector<int>vec;
for (int i = 0; i < Z[pos].size(); i++) {
if (used[Z[pos][i]] == true) continue;
vec.push_back(dfs2(Z[pos][i]));
}
sort(vec.begin(), vec.end());
int V = vec[max(0, (int)vec.size() - GG)];
if (vec.size() < GG && flag == false) V = 0;
return V + vec.size();
}
int main() {
scanf("%d%d%d", &N, &A, &B);
for (int i = 1; i <= N - 1; i++) {
scanf("%d%d", &E[i], &F[i]);
X[E[i]].push_back(F[i]);
X[F[i]].push_back(E[i]);
}
dfs1(B, 0);
for (int i = 0; i < 21; i++) {
for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i];
}
for (int i = 1; i <= N; i++) {
int v = lca(A, i);
val[i] = dist[v];
if (v == i) pl[dist[v]] = i;
else lis[dist[v]].push_back(i);
}
int Ans1 = 0, Ans2 = (1 << 30), dep = -1;
for (int i = 1; i <= N; i++) used[i] = false;
for (int i = 0; i < dist[A]; i++) {
for (int j = 0; j < lis[i].size(); j++) {
int u = lis[i][j], v = dp[u][0];
Z[u].push_back(v);
Z[v].push_back(u);
}
root = pl[i];
int B1 = (1 << 30), B2 = (1 << 30);
// Ans1 -> Ans1
dep += (int)Z[pl[i]].size();
if (dep <= 0) B1 = min(B1, Ans1 + (int)Z[pl[i]].size());
dep--;
// Ans1 -> Ans2
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
G = min(2 + i, 3); flag = true; int Z2 = dfs2(pl[i]);
B2 = min(B2, Ans1 + Z2);
// Ans2 -> Ans2
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
G = 1000000; flag = false; int Z3 = dfs2(pl[i]);
B2 = min(B2, Ans2 + Z3);
Ans1 = B1; Ans2 = max(Z2, B2);
}
cout << min(Ans1, Ans2) << endl;
return 0;
}
Compilation message
mousetrap.cpp:5:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
mousetrap.cpp: In function 'void dfs1(int, int)':
mousetrap.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int dfs2(int)':
mousetrap.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Z[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
mousetrap.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (vec.size() < GG && flag == false) V = 0;
~~~~~~~~~~~^~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < lis[i].size(); j++) {
~~^~~~~~~~~~~~~~~
mousetrap.cpp:106:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
^~~
mousetrap.cpp:106:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
^~~~
mousetrap.cpp:111:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
^~~
mousetrap.cpp:111:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
^~~~
mousetrap.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &A, &B);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &E[i], &F[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Incorrect |
7 ms |
1280 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
