Submission #349824

#TimeUsernameProblemLanguageResultExecution timeMemory
349824dooweyMousetrap (CEOI17_mousetrap)C++14
25 / 100
894 ms69272 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 100;
vector<int> T[N];

int trap;
int mouse;

int dfs(int u, int par){
    vector<int> lis;
    for(auto x : T[u]){
        if(x==par) continue;
        lis.push_back(dfs(x,u));
    }
    sort(lis.begin(),lis.end());
    int mx = 0;
    if(lis.size() >= 2){
        mx = lis[lis.size() - 2];
    }
    return (int)lis.size() + mx;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    cin >> trap >> mouse;
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    cout << dfs(mouse,trap);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...