#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, t, m;
vector<int> graph[1000001];
ll dp[1000001], ans = 0;
bool dfs(int node = t, int parent = 0) {
bool ret = false;
ll mx1 = 0, mx2 = 0;
for (int i : graph[node]) if (i != parent) {
ret |= dfs(i, node);
if (dp[i] >= mx1) mx2 = mx1, mx1 = dp[i];
else if (dp[i] > mx2) mx2 = dp[i];
}
dp[node] = graph[node].size() - 1 + mx2;
if (node == m) return ans += dp[node], true;
else return ans += (int(graph[node].size()) - 2) * ret, ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> t >> m;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
ans = -int(graph[t].size()) + 2;
dfs();
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
17 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23808 KB |
Output is correct |
5 |
Correct |
16 ms |
23808 KB |
Output is correct |
6 |
Correct |
17 ms |
23800 KB |
Output is correct |
7 |
Correct |
16 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23992 KB |
Output is correct |
10 |
Correct |
16 ms |
23788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
76660 KB |
Output is correct |
2 |
Correct |
332 ms |
71148 KB |
Output is correct |
3 |
Correct |
841 ms |
77548 KB |
Output is correct |
4 |
Correct |
386 ms |
50432 KB |
Output is correct |
5 |
Correct |
862 ms |
77420 KB |
Output is correct |
6 |
Correct |
839 ms |
77504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
17 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23808 KB |
Output is correct |
5 |
Correct |
16 ms |
23808 KB |
Output is correct |
6 |
Correct |
17 ms |
23800 KB |
Output is correct |
7 |
Correct |
16 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23992 KB |
Output is correct |
10 |
Correct |
16 ms |
23788 KB |
Output is correct |
11 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
17 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23808 KB |
Output is correct |
5 |
Correct |
16 ms |
23808 KB |
Output is correct |
6 |
Correct |
17 ms |
23800 KB |
Output is correct |
7 |
Correct |
16 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23992 KB |
Output is correct |
10 |
Correct |
16 ms |
23788 KB |
Output is correct |
11 |
Correct |
350 ms |
76660 KB |
Output is correct |
12 |
Correct |
332 ms |
71148 KB |
Output is correct |
13 |
Correct |
841 ms |
77548 KB |
Output is correct |
14 |
Correct |
386 ms |
50432 KB |
Output is correct |
15 |
Correct |
862 ms |
77420 KB |
Output is correct |
16 |
Correct |
839 ms |
77504 KB |
Output is correct |
17 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |