제출 #1344230

#제출 시각아이디문제언어결과실행 시간메모리
1344230gkos5678Torrent (COI16_torrent)C++20
31 / 100
2095 ms34512 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v) v.begin(), v.end()
#define len(v) (int)(v.size())
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int maxn = 3e5 + 7;

int n, a, b, nm, p[maxn], pi[maxn];
vi put, t[maxn];
vii ls[maxn];

void dfs1(int v){
    for (ii s : ls[v]){
        if (s.ff == p[v]) continue;
        p[s.ff] = v;
        pi[s.ff] = s.ss;
        dfs1(s.ff);
    }
}

int dfs2(int v, int pa = -1){
    t[v].clear();
    for (ii s : ls[v]){
        if (s.ff == pa || s.ss == nm) continue;
        t[v].pb(dfs2(s.ff, v));
    }
    sort(all(t[v]));
    int ret = 0;
    for (int i = len(t[v]) - 1; i >= 0; i--)
        ret = max(ret, t[v][i] + len(t[v]) - i);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> a >> b;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        ls[u].pb({v, i});
        ls[v].pb({u, i});
    }

    dfs1(a);
    int tr = b;
    while(tr != a){
        put.pb(pi[tr]);
        tr = p[tr];
    }
    reverse(all(put));
    int l = 0, r = n;
    while(l < r){
        int m = (l + r) / 2;
        int le = 0, ri = put.size() - 1;
        while(le < ri){
            int mi = (le + ri + 1) / 2;
            nm = put[mi];
            int tm = dfs2(a);
            if (tm <= m) le = mi;
            else ri = mi - 1;
        }
        nm = put[le];
        int t1 = dfs2(a), t2 = dfs2(b);
        if (max(t1, t2) > m) l = m + 1;
        else r = m;
    }

    cout << l << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...