BOJ 30690 선로 조립

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/30690

🧐 관찰 및 접근
#

암튼 트리가 있다
- 간선 하나를 떼고 다시 연결해서, 가장 많은 간선을 지나가고싶다.
- 간선 하나를 떼고 다시 연결해서, 트리의 지름을 최대로 하고 싶다.
- 쪼개진 두개의 트리에서, 각각의 지름 + 1이 답이다.
- 트리를 쓰는 트리 문제
  - 해당 문제에서, 해당 서브트리를 제외한 트리의 지름을 구할 수 있으면 되는 것 같다.
  - 이는 리루팅과 부모깊이, 다른 자식의 깊이 두개정도를 잘 들고있으면 가능하겠다.
    - 다른 자식의 지름도 들고있어야 한다!!
예제 트리 그림 ![[Drawing 2026-01-26 17.35.39.excalidraw.png]]

💻 풀이
#

코드 (C++):

int N, Q;
vector<int> links[200010];
int depth[200010];
vector<pii> childs[200010]; // {mxDepth, nodeIdx}
vector<pii> childs2[200010]; // {mxDiam, nodeIdx}
int diam[200010], upDepth[200010], upDiam[200010];

void dfs1(int cur, int par){
    vector<pii> ret;
    ret.push_back({0, cur});
    for(auto nxt: links[cur]){
        if(nxt == par) continue;
        depth[nxt] = depth[cur] + 1;
        dfs1(nxt, cur);
        diam[cur] = max(diam[cur], diam[nxt]);

        ret.push_back({childs[nxt][0].first + 1, nxt});
        sort(all(ret), greater<pii>());
        if((int)ret.size() > 3) ret.pop_back();

        childs2[cur].push_back({diam[nxt], nxt});
        sort(all(childs2[cur]), greater<pii>());
        if((int)childs2[cur].size() > 2) childs2[cur].pop_back();
    }
    childs[cur] = ret;
    if((int)ret.size() >= 2) diam[cur] = max(diam[cur], ret[0].first + ret[1].first);
    if((int)ret.size() >= 1) diam[cur] = max(diam[cur], ret[0].first);
}

void dfs2(int cur, int par, int mxUp){
    for(auto nxt: links[cur]){
        if(nxt == par) continue;
        vector<int> candidates;
        candidates.push_back(mxUp);
        for(auto [d, idx]: childs[cur]) if(idx != nxt) candidates.push_back(d);
        sort(all(candidates), greater<int>());

        if((int)candidates.size() >= 2) upDiam[nxt] = max(upDiam[nxt], candidates[0] + candidates[1]);
        if((int)candidates.size() >= 1) upDiam[nxt] = max(upDiam[nxt], candidates[0]);
        for(auto [d, idx]: childs2[cur]) if(idx != nxt) upDiam[nxt] = max(upDiam[nxt], d);
        upDiam[nxt] = max(upDiam[nxt], upDiam[cur]);
        dfs2(nxt, cur, candidates[0] + 1);
    }
}

void solve(){
    cin >> N >> Q;
    rep(i, 0, N-1){
        int u, v; cin >> u >> v;
        links[u].push_back(v);
        links[v].push_back(u);
    }

    dfs1(1, -1);
    dfs2(1, -1, 0);

    // rep(i, 1, N+1) cout << diam[i] << " "; cout << "\n";
    // rep(i, 1, N+1) cout << upDiam[i] << " "; cout << "\n";
    while(Q--){
        int u, v; cin >> u >> v;
        if(depth[u] < depth[v]) swap(u, v);
        cout << diam[u] + upDiam[u] + 1 << "\n";
    }
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#