結果
| 問題 |
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;
}