LCA

📝 문제 정보 # 링크: 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/1734 🧐 관찰 및 접근 # 무향 그래프 $G = (V, E)$가 주어진다. 여기서 두가지 쿼리가 주어진다. 간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 각각 살펴보자. 먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3176 🧐 관찰 및 접근 # 도로가 N-1개인걸 보니 트리겠구만 이때 경로상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하라는데… HLD를 써도 되지만, sparse table에서의 RMQ처리처럼 진행해도 큰 문제가 없겠다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } dfs(1, -1, 0); rep(j, 1, 20) rep(i, 1, N+1) if(par[i][j-1]){ par[i][j] = par[par[i][j-1]][j-1]; mnDist[i][j] = min(mnDist[i][j-1], mnDist[par[i][j-1]][j-1]); mxDist[i][j] = max(mxDist[i][j-1], mxDist[par[i][j-1]][j-1]); } int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; auto [mn, mx] = calc(u, v); cout << mn << ' ' << mx << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1761 🧐 관찰 및 접근 # 트리에서, 두 정점 사이의 경로는 유일하다. 해당 경로는 두 정점의 LCA를 지난다. 두 점 사이의 거리는 $d(u) + d(v) - 2*d(\text{LCA}(u, v))$로 계산할 수 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int _par){ for(auto [nxt, w]: links[cur]){ if(nxt == _par) continue; dist[nxt] = dist[cur] + w; depth[nxt] = depth[cur] + 1; par[nxt][0] = cur; dfs(nxt, cur); } } int LCA(int u, int v){ if(u == v) return u; if(depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; rep(i, 0, 16) if((diff >> i) & 1) u = par[u][i]; if(u == v) return u; rrep(i, 16, 0){ if(par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } return par[u][0]; } ll getDist(int u, int v){ int lca = LCA(u, v); return dist[u] + dist[v] - 2 * dist[lca]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } dfs(1, -1); rep(j, 1, 16) rep(i, 1, N+1) par[i][j] = par[par[i][j-1]][j-1]; cin >> Q; while(Q--){ int u, v; cin >> u >> v; cout << getDist(u, v) << '\n'; } } 🔒 구현 코드 잠금