제출 #1353571

#제출 시각아이디문제언어결과실행 시간메모리
1353571goulthenMousetrap (CEOI17_mousetrap)C++20
0 / 100
150 ms74648 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 1e6+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
vector<int> g[MAXN];
int dp[MAXN], dep[MAXN];

void dfs(int u, int p =-1) {
    vector<int> ls;
    for(int &v : g[u])if(v!=p) {
        dep[v] = dep[u]+1;
        dfs(v,u);
        ls.pb(dp[v]);
    }
    dep[u]+=ls.size()-1;
    sort(ls.rbegin(), ls.rend());
    if(ls.size()>1) dp[u] = dp[ls[1]]+ls.size()-1;
}

void solve() {
    int n,m,t; cin >> n >> t >> m;
    rep(i,1,n-1) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(t);
    cout << dp[m] + dep[m] << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int tt = 1;
    //cin >> tt;
    
    while(tt--) solve();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…