Euler_Tree_Technic

📝 문제 정보 # 링크: 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"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/19641 🧐 관찰 및 접근 # $A_{left} < B_{left} < B_{right} < A_{right}$라면 두 노드를 포함관계라고 한다. 이는 트리를 dfs적으로 접근하면서, 트리에 들어가는 시간 / 나가는 시간을 기록함으로써 얻어낼 수 있다. 💻 풀이 # 코드 (C++): int N; vector<int> links[100010]; int start[100010], ed[100010]; int timer = 1; void dfs(int cur, int par){ start[cur] = timer++; for(auto nxt: links[cur]) if(nxt != par) dfs(nxt, cur); ed[cur] = timer++; } void solve(){ cin >> N; rep(i, 0, N){ int node; cin >> node; while(true){ int x; cin >> x; if(x == -1) break; links[node].push_back(x); } sort(all(links[node])); } int S; cin >> S; dfs(S, -1); rep(i, 1, N+1) cout << i << ' ' << start[i] << ' ' << ed[i] << '\n'; } 🔒 구현 코드 잠금