Tree

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31740 🧐 관찰 및 접근 # 문제에서 주어진 그래프는 트리로 보인다. 트리에서는 모든 간선이 단절선이므로 하나만 잘라도 두 컴포넌트로 나뉘는것이 자명하다. 간선을 하나 자르고 나면 서브트리 하나와 나머지 부분으로 나뉜다. 서브트리의 가중치는 트리DP를 활용해 미리 계산해둘 수 있고, 나머지 부분은 전체 가중치 합에서 해당 서브트리의 가중치 합만큼을 빼면 된다. $O(N)$에 계산 가능해보인다. 💻 풀이 # 코드 (C++): int dfs(int c, int p){ par[c] = p; DP[c] = W[c]; for(auto nxt : links[c]){ if(nxt == p) continue; DP[c] += dfs(nxt, c); } return DP[c]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } rep(i, 1, N+1) cin >> W[i]; int SUM = dfs(1, -1); int ans = 2e9; pii ans2 = {-1, -1}; rep(i, 2, N+1) if(ans > abs(DP[i] - (SUM - DP[i]))){ ans = abs(DP[i] - (SUM - DP[i])); ans2 = {i, par[i]}; } cout << ans << '\n'; cout << ans2.first << ' ' << ans2.second << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30208 🧐 관찰 및 접근 # 업무들의 순서때문에, 자유롭게 선택하지 못하는 경우들이 생긴다. 이게 어떤 느낌이지? ![[Drawing 2026-02-07 15.51.45.excalidraw.png]] 예제 입력 1의 순서는 다음과 같다. $1 \rightarrow 2 \rightarrow 3$을 보자. $1$까지 수행해서 중요도 $w_1$, 처리시간 $t_1$을 얻을 수 있다. $2$까지 수행해서 중요도 $w_1 + w_2$, 처리시간 $t_1 + t_2$를 얻을 수 있다. $3$까지 수행해서 $\cdots$ 저렇게 물건을 만들고 나면, 세개중에서 택1을 하는것 빼고는 배낭문제와 동일해진다. 트리 dfs로 냅색을 잘 돌면서 DP를 할 수 있을 것 같다. 근데 안에서 분기가 일어나면… 0이 아닌 모든 $p_i$들은 모두 다르다 라는 문장이 입력에 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int root, int w, int t){ w += W[cur]; t += T[cur]; bags[root].push_back({w, t}); for(auto nxt: links[cur]) dfs(nxt, root, w, t); } void solve(){ cin >> N >> S; rep(i, 1, N+1) cin >> W[i]; rep(i, 1, N+1) cin >> T[i]; rep(i, 1, N+1){ int p; cin >> p; links[p].push_back(i); } for(auto nxt: links[0]) dfs(nxt, nxt, 0, 0); rep(i, 0, N+2) rep(j, 0, S+1) KS[i][j] = 1e9; KS[0][0] = 0; rep(i, 0, N+1) rep(j, 0, S+1) { KS[i+1][j] = min(KS[i+1][j], KS[i][j]); for(auto [w, t]: bags[i]){ int nxt = min(S, j + w); // } KS[i+1][nxt] = min(KS[i+1][nxt], KS[i][j] + t); } } if(KS[N+1][S] == 1e9) cout << -1; else cout << KS[N+1][S]; } 🔒 구현 코드 잠금

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

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14675 🧐 관찰 및 접근 # 트리에서의 단절점과 단절선을 생각해보자. 트리에서 모든 간선은 단절선이다. 사이클 없는 연결 그래프니까 트리에서 리프노드를 제외한 모든 노드는 단절점이다. 위와 이유가 같다. 우회경로로 쓸 back edge가 없다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } cin >> Q; while(Q--){ int t, k; cin >> t >> k; if(t == 1) cout << ((int)links[k].size() == 1 ? "no\n" : "yes\n"); else cout << "yes\n"; } } 🔒 구현 코드 잠금

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

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32144 🧐 관찰 및 접근 # 문제에 내 이름이 나와서 기분이 좋다. 서브트리를 하나 잡아서, 그 서브트리의 루트와 그 부모와의 연결을 끊고 서브트리의 임의의 정점과 방금 끊은 부모를 연결하는 연산을 할 수 있다. 직관적으로, 해당 서브트리에서 줄 수 있는 길이의 가중치가 깊이에서 지름으로 바뀜을 알 수 있다. Tree DP를 이용한 트리의 지름 구하기 방법을 이용하면 좋을 것 같다. ![[Drawing 2026-01-25 10.09.49.excalidraw.png]] 위와 같은 경우같은게 발생할 것 같다. 두번째로 작은 트리의 지름과 마찬가지로, 기존 지름의 양 끝 점중 한 점은 유지된다. …인줄알았는데 안된다. ![[Drawing 2026-01-25 11.07.01.excalidraw.png]] 다음과 같이 서브노드 안에 기존 트리의 지름이 다 있는 경우도 있다… 결국 문제에서도 말하는 것처럼 문제를 부분트리와 그 나머지로 보면, 리루팅이 가능하지 않을까? 리루팅을 이용해서, 다음과 같은 정보를 저장하자. 서브트리의 지름 해당 서브트리에서 가장 깊은 깊이 두개 (리루팅용) 해당 노드에서 위로 갔을때, 가장 깊은 길이 이는 dfs를 이용해서 구현 가능하고, 시간복잡도는 $O(N)$이다. 디버깅을 위한 예제 2번 그림 ![[Drawing 2026-01-25 10.30.52.excalidraw.png]] 💻 풀이 # 코드 (C++): 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"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/19581 🧐 관찰 및 접근 # 가중치 없는 트리인줄 알고, 당연히 지름-1이 답이 아닌가? 했더니 가중치가 있었다 가중치가 있는 트리라면, 우리가 원래 쓰던 DFS두번이라는 방법은 쉽지 않을것같다 가장 긴 트리의 지름과, 두번째로 긴 트리의 지름이 아예 관계 없는 곳에 있을 수도 있지 않을까? 아닌가? ![[Drawing 2026-01-25 09.41.32.excalidraw.png]] 트리의 지름과 두번째 트리의 지름이 끝 정점을 공유하지 않는다고 하자. 그렇다면, 위 그림과 같이 압축해서 나타낼 수 있다. 이 때, $a + b = D_1 \geq c + d = D_2$라 하자. 일반성을 잃지 않고 $a \geq b, c \geq d$라 하자. 서로 공유하는 정점 하나가 있는 경우 $a + c \geq D_1/2 + D_2/2 \geq D_2$ 이므로, a와 c를 지나는 경로가 우리가 가정한 두번째 지름보다 더 크거나 같다. 더 큰 경우 모순이고 같은 경우 $a+c$를 두번째 지름으로 택해도 아무 문제가 없다. 서로 공유하는 정점이 없는경우 (다른 서브트리에 나타낼 수 있는 경우) $a + c + e + f \geq D_1/2 + D_2/2 + e + f > D_2$ 이므로, $D_2$의 경로는 두번째 트리의 지름이 아니다. 따라서, 트리의 두번째 지름의 한 끝점은 트리의 지름의 한 끝점과 같다. DFS를 돌려서 트리의 지름 양 끝 점을 찾고, 거기서부터 두번째지름을 한번씩 찾아주자. 💻 풀이 # 코드 (C++): vector<pii> dfs(int cur, int par){ vector<pii> v; v.push_back({0, cur}); for(auto [nxt, w]: links[cur]){ if(nxt == par) continue; auto nv = dfs(nxt, cur); rep(i, 0, min(2, (int)nv.size())){ v.push_back({nv[i].first + w, nv[i].second}); } sort(all(v), greater<pii>()); while(v.size() > 2) v.pop_back(); } return v; } 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}); } int L = dfs(1, -1)[0].second; // 트리의 지름의 한쪽 끝 int ans = 0; auto ret = dfs(L, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 1 int R = ret[0].second; // 트리의 지름의 다른쪽 끝 ret = dfs(R, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 2 cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5639 🧐 관찰 및 접근 # 이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자! 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데… 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다. 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로 50 (루트) --- 30 (왼쪽 서브트리) 24 5 28 45 --- 98 (오른쪽 서브트리) 52 60 첫 입력에 대해, 이렇게 생각할 수 있지 않을까? 그리고 각 서브트리 또한 이진 검색트리이므로, 이를 재귀적으로 수행할 수 있다. 예를 들어, 왼쪽 서브트리에 대해서 30 (루트) --- 24 (왼쪽 서브트리) 5 28 --- 45 (오른쪽 서브트리) 위와 같이 말이다! 그렇다면, 재귀를 이용해서 트리를 구축하고 후위순회만 하면 끝난다. 💻 풀이 # 코드 (C++): vector<int> v; struct Node{ int val = -1; Node* left = nullptr; Node* right = nullptr; Node(int s, int e){ val = v[s]; if(s == e) return; int idx = e+1; rep(i, s+1, e+1){ if(v[i] > val){ idx = i; break; } } if(s+1 <= idx-1) left = new Node(s+1, idx-1); if(idx <= e) right = new Node(idx, e); } }; void postorder(Node* node){ if(node == nullptr) return; postorder(node->left); postorder(node->right); cout << node->val << '\n'; } void solve(){ int x; while(cin >> x) v.push_back(x); Node* root = new Node(0, v.size()-1); postorder(root); } 🔒 구현 코드 잠금