提出 #63129366

---

ソースコード 拡げる

// जय श्री राम

/*
    Terence Tao: If you can't solve a problem, try to solve a simpler problem.
    Richard P. Feynman: You don't need to have some magic to understand complex things. People just work really really hard.
*/

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include<algo/debug.cpp>
#else
#define debug(...)
#define debugArr(...)
#endif
using namespace std;

const int N = 200001;

int n;
vector<vector<int>> tree(N+1, vector<int>());
vector<int> contri(N+1, 0);
int ans = 0;

void dfs(int node, int par) {
    for(auto& child : tree[node]) {
        if(child == par)
            continue;
        dfs(child, node);
    }
    vector<int> vals;
    for(auto& child : tree[node]) {
        if(child == par)
            continue;
        vals.push_back(contri[child]);
    }
    sort(vals.rbegin(), vals.rend());
    if(vals.size() >= 4) {
        ans = max(ans, 1 + vals[0] + vals[1] + vals[2] + vals[3]);
        contri[node] = 1 + vals[0] + vals[1] + vals[2];
    } else if(vals.size() == 3) {
        contri[node] = 1 + vals[0] + vals[1] + vals[2];
        if(vals[0] >= 4)
            ans = max(ans, 1 + vals[0]);
    } else if(vals.size() >= 1) {
        contri[node] = 1;
        if(vals[0] >= 4)
            ans = max(ans, 1 + vals[0]);
    } else {
        contri[node] = 1;
    }
    debug(node, vals, contri[node]);
}

void solve() {
    cin >> n;
    int v1,v2;
    for(int i=1;i<n;i++) {
        cin >> v1 >> v2;
        tree[v1].push_back(v2);
        tree[v2].push_back(v1);
    }
    dfs(1,-1);
    if(ans == 0)
        ans = -1;
    cout << ans << "\n";
}

int main() {
    #ifdef case3_local
        auto begin = std::chrono::high_resolution_clock::now();
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    // cin >> t;
    while(t--) {
        solve();
    }
    #ifdef case3_local
        auto end = std::chrono::high_resolution_clock::now();
        cerr << setprecision(4) << fixed;
        cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
    #endif
    return 0;
}

提出情報

ジャッジ結果