64852023-12-04 21:29:42szilHosszú Láncokcpp17Időlimit túllépés 30/100600ms16456 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define MAX(a, b) (a) = max((a), (b))
#define MIN(a, b) (a) = min((a), (b))
#define all(a) (a).begin(), (a).end()
#define sortedpair(a, b) {min((a), (b)), max((a), (b))}

const ll MOD = 1e9+7;

int n;
vector<vector<int>> v;

int dfs(int x, int m, int p = -1){
    multiset<int> c;
    int nagyobb = 0;
    for(int i : v[x]){
        if(i == p)continue;
        int t = dfs(i, m, x);
        if(t == -1)return -1;
        if(t >= m)nagyobb++;
        else c.insert(t);
    }
    if(c.empty()){
        if(nagyobb)return m+1;
        else return 1;
    }
    auto it = c.begin();
    bool nemsikerult = false;
    while(it != c.end() && c.size() >= 2){
        auto it2 = c.lower_bound(m-*it);
        if(it == it2)it2++;
        if(it2 == c.end()){
            if(nagyobb){
                it = c.erase(it);
                nagyobb--;
            } else {
                if(nemsikerult)
                    return -1;
                nemsikerult = true;
                it++;
                continue;
            }
        }
        it = c.erase(it);
        if(it == it2){
            it = c.erase(it);
        } else {
            c.erase(it2);
        }
    }

    if(c.size() == 0){
        if(nagyobb)return m+1;
        return 1;
    }
    if(nagyobb >= 2)return m+1;
    return *c.begin()+1;


    // multiset<int> c; // konstans ??
    // for(int i : v[x]){
    //     if(i == p)continue;
    //     int t = dfs(i, m, x);
    //     if(t == -1)return -1;
    //     c.insert(t);
    // }
    // if(c.empty()) return 1;
    // auto it = c.begin();
    // while(it != c.end() && *it < (m+1)/2){
    //     auto it2 = c.lower_bound(m-*it);
    //     if(it2 == c.end()){
    //         it++;
    //         continue;
    //     }
    //     it = c.erase(it);
    //     if(it == it2){
    //         c.erase(it);
    //         break;
    //     }
    //     c.erase(it2);
    // }
    // if(c.empty()){
    //     return 1;
    // }
    // if(*c.begin() >= (m+1)/2){
    //     if(c.size() % 2 == 1) return 1 + *c.rbegin();
    //     else return 1;
    // }
    // if(c.size() == 1){
    //     return *c.begin()+1;
    // }
    // if(*next(c.begin()) < (m+1)/2){
    //     return -1;
    // }
    // if(c.size()%2 == 0){
    //     return -1;
    // }
    // return 1 + *c.begin();
    // while(*c.begin() < m && c.size() >= 2){
    //     c.erase(c.begin()); c.erase(c.begin());
    // }
    // if(c.empty()) return 1;
    // return *c.rbegin() + 1;
}

void solve(){
    cin>>n;
    v.assign(n, {});
    for(int i = 0; i < n-1; i++){
        int a, b; cin>>a>>b; a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int start = 0;
    for(int i = 0; i < n; i++){
        if(v[i].size() == 1) {
            start = i;
            break;
        }
    }

    if(v[v[start][0]].size() == n-1){
        cout<<(n%2 == 1 ? 2 : 1)<<endl;
        return;
    }

    int l = 1, r = n-1;
    while(l < r){
        int m = (l+r+1)/2;
        int res = dfs(start, m);
        if(res > m || res == 1){
            l = m;
        } else {
            r = m-1;
        }
    }
    cout<<l<<endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t = 1;
    // cin >> _t;
    while (_t--) {
        solve();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Elfogadva3ms2020 KiB
3Elfogadva3ms2252 KiB
4Elfogadva3ms2464 KiB
subtask210/10
5Elfogadva3ms2676 KiB
6Elfogadva3ms2916 KiB
7Elfogadva3ms3124 KiB
8Elfogadva2ms3184 KiB
9Elfogadva3ms3416 KiB
10Elfogadva3ms3532 KiB
11Elfogadva3ms3752 KiB
12Elfogadva3ms3824 KiB
13Elfogadva3ms4036 KiB
14Elfogadva3ms4128 KiB
15Elfogadva3ms4224 KiB
subtask30/20
16Elfogadva3ms4124 KiB
17Elfogadva3ms4224 KiB
18Időlimit túllépés574ms3484 KiB
19Elfogadva3ms4352 KiB
20Elfogadva3ms4436 KiB
21Elfogadva3ms4568 KiB
22Elfogadva3ms4788 KiB
23Elfogadva3ms4784 KiB
subtask420/20
24Elfogadva3ms4784 KiB
25Elfogadva3ms4868 KiB
26Elfogadva3ms4808 KiB
27Elfogadva3ms5140 KiB
28Elfogadva3ms5184 KiB
29Elfogadva3ms5280 KiB
30Elfogadva3ms5184 KiB
31Elfogadva3ms5296 KiB
subtask50/50
32Elfogadva7ms5872 KiB
33Elfogadva12ms7180 KiB
34Időlimit túllépés600ms7096 KiB
35Elfogadva54ms15788 KiB
36Elfogadva8ms6168 KiB
37Elfogadva18ms7488 KiB
38Elfogadva45ms10980 KiB
39Elfogadva122ms16456 KiB