#1120479 (C++17) No.1976 Cut then Connect

• 問題: No.1976 Cut then Connect
• ユーザー: yuriko32
• 提出日時: 2025-09-11 01:45:45
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 7,062 bytes
• コンパイル時間: 2,506 ms
• コンパイル使用メモリ: 203,540 KB
• 実行使用メモリ: 10,880 KB
• 最終ジャッジ日時: 2025-09-11 01:45:51
• 合計ジャッジ時間: 6,038 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 1 WA * 1
other	AC * 7 WA * 24

ソースコード

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF_NEG = -1000000000;

int N;
vector<vector<int>> g;
vi parent_node;
vi depth_down;   // depth_down[u] = max distance from u to a node in its subtree (edges)
vi diam_sub;     // diameter of subtree rooted at u (edges)
vi up_depth;     // distance from u to farthest node outside its subtree (edges), or -INF if none
vi up_diam;      // diameter of the component outside u's subtree (edges)

void dfs1(int u, int p){
    parent_node[u] = p;
    depth_down[u] = 0;
    diam_sub[u] = 0;
    // collect children's depth_down and diam_sub
    vector<int> topDepths; topDepths.reserve(g[u].size());
    for(int v: g[u]){
        if(v==p) continue;
        dfs1(v, u);
        topDepths.push_back(depth_down[v]);
        diam_sub[u] = max(diam_sub[u], diam_sub[v]);
    }
    // set depth_down[u]
    int best = -1;
    for(int d: topDepths) if(d > best) best = d;
    if(best >= 0) depth_down[u] = best + 1;
    else depth_down[u] = 0;

    // maybe path through u uses top two child depths
    int a=-1,b=-1;
    for(int d: topDepths){
        if(d > a){ b = a; a = d; }
        else if(d > b){ b = d; }
    }
    if(a >= 0 && b >= 0){
        diam_sub[u] = max(diam_sub[u], a + b + 2);
    } else if(a >= 0){
        // path between u and deepest node in its child
        diam_sub[u] = max(diam_sub[u], a + 1);
    } else {
        // leaf: diam_sub[u] = 0 already
    }
}

void dfs2(int u, int p){
    // prepare arrays of candidates from children: depth_down[child] and diam_sub[child]
    int deg = g[u].size();
    // collect children (exclude parent)
    vector<int> children;
    for(int v: g[u]) if(v != p) children.push_back(v);
    int k = children.size();

    // precompute for siblings: max diam_sub among children, also top two depth_down among children
    // We will need prefix/suffix maxima for diam_sub and depth_down to exclude a child quickly.
    vector<int> prefMaxDiam(k+1, INT_MIN), sufMaxDiam(k+1, INT_MIN);
    for(int i=0;i<k;i++){
        prefMaxDiam[i+1] = max(prefMaxDiam[i], diam_sub[children[i]]);
    }
    for(int i=k-1;i>=0;i--){
        sufMaxDiam[i] = max(sufMaxDiam[i+1], diam_sub[children[i]]);
    }

    // for depths (depth_down[child] + 1 is distance from parent u to deepest in that child)
    vector<int> prefBestDepth(k+1, INF_NEG), sufBestDepth(k+1, INF_NEG);
    for(int i=0;i<k;i++){
        int val = depth_down[children[i]] + 1; // distance from u to deepest in that child
        prefBestDepth[i+1] = max(prefBestDepth[i], val);
    }
    for(int i=k-1;i>=0;i--){
        int val = depth_down[children[i]] + 1;
        sufBestDepth[i] = max(sufBestDepth[i+1], val);
    }

    // For combining two best among { up_depth[u], depth_down[sibling]+1 }, we may need top two.
    // We'll compute for each child its up_depth and up_diam then recurse.
    for(int i=0;i<k;i++){
        int v = children[i];
        // compute max diam among siblings (exclude v)
        int maxSiblingDiam = max(prefMaxDiam[i], sufMaxDiam[i+1]);
        if(maxSiblingDiam == INT_MIN) maxSiblingDiam = INF_NEG;

        // compute best depth among siblings (distance from u)
        int bestSibDepth = max(prefBestDepth[i], sufBestDepth[i+1]); // could be INF_NEG
        // candidates for distances from u to nodes not in v-subtree:
        // - up_depth[u] (distance from u to outside of u-subtree)
        // - bestSibDepth (distance from u to deepest in any sibling)
        // - also node u itself distance 0 (but when computing up_depth[v] at child we consider at least distance 1 to parent)
        int cand1 = up_depth[u]; // maybe -INF
        int cand2 = bestSibDepth; // maybe -INF

        // compute up_depth[v] (distance from v to farthest node outside v-subtree)
        // options:
        //  - go to parent u: distance 1 (to reach u)
        //  - go to parent then to outside via up_depth[u]: 1 + up_depth[u]
        //  - go to parent then to sibling deepest: 1 + bestSibDepth
        int bestToOutside = 1; // at least can reach parent (distance 1)
        if(cand1 > INF_NEG) bestToOutside = max(bestToOutside, 1 + cand1);
        if(cand2 > INF_NEG) bestToOutside = max(bestToOutside, 1 + cand2);
        up_depth[v] = bestToOutside;

        // compute up_diam[v] (diameter of component outside v-subtree)
        int cur = INF_NEG;
        // include up_diam[u]
        if(up_diam[u] > cur) cur = up_diam[u];
        // include diameters of siblings
        if(maxSiblingDiam > cur) cur = maxSiblingDiam;
        // include path that goes through u combining two best among { up_depth[u], depth_down[sib]+1 }
        // collect top two
        int x = INF_NEG, y = INF_NEG;
        if(cand1 > x){ y = x; x = cand1; }
        else if(cand1 > y){ y = cand1; }
        if(cand2 > x){ y = x; x = cand2; }
        else if(cand2 > y){ y = cand2; }
        // best single (distance from u to farthest outside)
        if(x > cur) cur = x;
        // pair
        if(y > INF_NEG){
            cur = max(cur, x + y);
        }
        // Note: cur might still be INF_NEG if there is truly nothing outside (possible when u is root and no siblings)
        if(cur == INF_NEG) cur = 0; // empty component -> diameter 0
        up_diam[v] = cur;

        // recurse
        dfs2(v, u);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // read tree
    int k_dummy;
    if(!(cin >> k_dummy)) return 0; // reuse var name not used
    // Actually first input is number of nodes? Problem statement here only the abstract; assume next is N and then edges?
    // For safety: this program assumes next integer is N, followed by N-1 parents: for i=2..N read parent.
    // But to be generic, let's assume input: N then N-1 lines edges or parent array. Here we follow parental array style.
    // However original user's preceding problems used parent-array format. We'll assume same: first read N then next N-1 parents for 2..N.
    int Nread = k_dummy;
    N = Nread;
    g.assign(N+1, {});
    parent_node.assign(N+1, 0);
    depth_down.assign(N+1, 0);
    diam_sub.assign(N+1, 0);
    up_depth.assign(N+1, INF_NEG);
    up_diam.assign(N+1, 0);

    // read parent array style: next N-1 integers a2..aN
    for(int i=2;i<=N;i++){
        int a; cin >> a;
        g[a].push_back(i);
        g[i].push_back(a);
    }

    // root at 1
    dfs1(1, 0);
    // for root: up_depth[root] = INF_NEG (no outside), up_diam[root] = 0
    up_depth[1] = INF_NEG;
    up_diam[1] = 0;
    dfs2(1, 0);

    // now for every edge parent-child (p - v where parent_node[v] == p), consider cut there
    long long ans = LLONG_MAX;
    for(int v=2; v<=N; ++v){
        int p = parent_node[v];
        int d1 = diam_sub[v];
        int d2 = up_diam[v];
        // radius = ceil(d/2) = (d+1)/2 using integer
        int r1 = (d1 + 1) / 2;
        int r2 = (d2 + 1) / 2;
        int cand = max( max(d1, d2), r1 + 1 + r2 );
        ans = min<long long>(ans, cand);
    }
    if(ans==LLONG_MAX) ans = 0;
    cout << ans << "\n";
    return 0;
}