BOJ 32144 트리를 쓰는 트리 문제

int N;
vector<int> links[300005];
vector<pii> max_depth[300005];
int diam[300005];
int updepth[300005], updiam[300005];

vector<pii> dfs(int cur, int par){
    vector<pii> v;
    v.push_back({0, cur});
    for(auto nxt: links[cur]){
        if(nxt == par) continue;
        auto nv = dfs(nxt, cur);
        diam[cur] = max(diam[cur], diam[nxt]);
        v.push_back({nv[0].first + 1, nxt});
        sort(all(v), greater<pii>());
        while(v.size() > 2) v.pop_back();
    }
    if(v.size() >= 2) diam[cur] = max(diam[cur], v[0].first + v[1].first);
    else diam[cur] = max(diam[cur], v[0].first);
    max_depth[cur] = v;

    // cout << "cur: " << cur << " diam: " << diam[cur] << " max_depth: ";
    // for(auto p: v) cout << "(" << p.first << "," << p.second << ") ";
    // cout << '\n';
    return v;
}

void dfs2(int cur, int par){
    for(auto nxt: links[cur]){
        if(nxt == par) continue;

        updepth[nxt] = updepth[cur] + 1;
        if(max_depth[cur][0].second != nxt) updepth[nxt] = max(updepth[nxt], max_depth[cur][0].first + 1);
        else if(max_depth[cur].size() >= 2) updepth[nxt] = max(updepth[nxt], max_depth[cur][1].first + 1);
        dfs2(nxt, cur);
    }
}

void solve(){
    cin >> N;
    rep(i, 2, N+1){
        int p; cin >> p;
        links[p].push_back(i);
        links[i].push_back(p);
    }

    dfs(1, -1);
    dfs2(1, -1);
    rep(i, 2, N+1) cout << max(diam[1], updepth[i] + diam[i]) << "\n";
}