BOJ 35288 Designant.

Table of Contents

📝 문제 정보
#

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

🧐 관찰 및 접근
#

문제를 정리하면 다음과 같다.
- 트리가 주어진다.
- 간선을 $K$개 지워서 포레스트로 만든다.
- 포레스트를 잘 합쳐서 트리의 지름이 최소가 되도록 하자.
포레스트를 잘 합치는 문제는 빌라봉으로 유명하다.
- 이 문제에 따르면, 세개 이상의 트리를 합칠 때, 가장 긴 트리의 지름 세개를 $a \geq b \geq c$ 라고 하면
- 그 결과는 $\max(a, \lceil\frac{a}{2}\rceil + \lceil\frac{b}{2}\rceil + 1, \lceil\frac{b}{2}\rceil + \lceil\frac{c}{2}\rceil + 2)$
- 결과는 위와 같고, 이는 새로 만든 간선을 $0, 1, 2$개 이용하는 경로중 가장 긴것과 같다.
  - 그리디하게 가장 긴 지름의 중심에 다른 중심들을 이은 모양에서 나온 결과이다.
그렇다면 트리를 빠르게 쪼개서 지름만 빠르게 계산할 수 있으면 되는 것 같다.
- 이걸 어떻게 할 수 있을까?
예제 1번의 트리를 ETT를 하면서 그려보자.
- ![[Drawing 2026-02-25 22.49.23.excalidraw.png]]
- 그리고 세번째 쿼리를 생각해보자.
  - $(1, 2), (3, 6), (4, 5, 7)$으로 나뉘어야 하는디…
  - ETT로 생각하면, $(1, 2, (5, (3, 6), 4, 7))$ 같은 느낌으로 그룹지어지는건가?
  - 잘 처리된 부분들은 상관 없는데, $(5, 4, 7)$같은데서 지름을 어떻게 구하면 좋을지 감이 안온다.
  - 일단 저걸 $(5), (4,7)$ 두 덩어리를 합치는 연산으로 보자. 오일러 투어 테크닉을 적용하면 연속 구간에 속하는 노드들의 지름은 세그먼트 트리로 구할 수 있다고 한다.
    - 이걸 어떻게 하는거지?
  - 트리 두개의 지름의 양끝 점을 각각 $(a, b), (c, d)$ 라고 할때
  - 두 트리를 합친곳에서의 지름은 $(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)$중에서 존재한다.
  - 이를 pull연산으로 잘 정의해보자.
구현이 상당히 어렵다..

💻 풀이
#

코드 (C++):

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

    auto [ETT_in, ETT_out] = ETT(N, links);
    vector<int> ETT_inv(N+1);
    rep(i, 1, N+1) ETT_inv[ETT_in[i]] = i;

    LCA_Tree = new Tree_LCA(N+1, links);
    vector<Node> nodes(N+1);
    rep(i, 1, N+1) nodes[i] = Node(ETT_inv[i], ETT_inv[i], 0);
    SegmentTreeNode seg(N+1, nodes);

    vector<int> edge_to_subtree(N-1);
    rep(i, 0, N-1){
        auto [u, v] = edges[i];
        if(LCA_Tree->depth[u] < LCA_Tree->depth[v]) swap(u, v);
        edge_to_subtree[i] = u;
    }

    while(Q--){
        int K; cin >> K;
        vector<int> cuts(K);
        rep(i, 0, K) cin >> cuts[i];
        vector<Node> Query_nodes;
        vector<pair<int, bool>> events; // {ETT_idx, is_end}
        for(auto c: cuts){
            int u = edge_to_subtree[c-1];
            events.push_back({ETT_in[u], false});
            events.push_back({ETT_out[u], true});
        }
        sort(all(events));
        int cur = 1;
        stack<Node> stk;
        stk.push(Node());
        for(auto [idx, is_end]: events){
            if(is_end){
                Node& top = stk.top();
                top = seg.pull(top, seg.query(cur, idx));
                cur = idx+1;
                Query_nodes.push_back(top);
                stk.pop();
            }
            else{
                Node& top = stk.top();
                top = seg.pull(top, seg.query(cur, idx-1));
                cur = idx;
                stk.push(Node());
            }
        }
        Node& top = stk.top();
        top = seg.pull(top, seg.query(cur, N));
        Query_nodes.push_back(top);
        sort(all(Query_nodes), [](Node a, Node b){
            return a.dist > b.dist;
        });
        int ans = 0;
        if(Query_nodes.size() > 0) ans = Query_nodes[0].dist;
        if(Query_nodes.size() > 1) ans = max(ans, (Query_nodes[0].dist+1)/2 + (Query_nodes[1].dist+1)/2 + 1);
        if(Query_nodes.size() > 2) ans = max(ans, (Query_nodes[1].dist+1)/2 + (Query_nodes[2].dist+1)/2 + 2);
        cout << ans << "\n";
    }
}

🔒

구현 코드 잠금

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

🛒 쿠팡 방문하고 코드 보기

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

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#