This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, t, m;
vector<ll> g[1000009];
ll trap[1000009];
ll dp[1000009];
ll ans[1000009];
void dfs(ll v, ll prt){
if(v == t){
trap[v] = 1;
return;
}
for(auto u : g[v])
if(u != prt){
dfs(u, v);
if(trap[u])
trap[v] = 1;
}
pii maxi = {0, 0};
ll edgecnt = 0;
for(auto u : g[v])
if(u != prt && trap[u] == 0){
if(dp[u] >= maxi.ff){
maxi.ss = maxi.ff;
maxi.ff = dp[u];
}
else if(dp[u] >= maxi.ss)
maxi.ss = dp[u];
++edgecnt;
}
dp[v] = edgecnt+maxi.ss;
ans[v] = edgecnt;
if(v == m)
ans[v] += maxi.ss;
for(auto u : g[v])
if(u != prt && trap[u]){
dp[v] += dp[u];
ans[v] += ans[u];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> t >> m;
for(ll i = 0; i < n-1; ++i){
ll x, y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs(m, 0);
cout << ans[m] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |