📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16964 🧐 관찰 및 접근 # dfs를 돌리듯이 지금까지 걸어온 과정들을 기록하면서 다음 노드를 갈 수 있었는가?를 체크하자. 💻 풀이 # 코드 (C++): import sys input = sys.stdin.readline N = int(input()) links = [set() for _ in range(N + 1)] for _ in range(N-1): a, b = map(int, input().split()) links[a].add(b) links[b].add(a) lst = list(map(int, input().split())) if lst[0] != 1: print(0) exit() nidx = 1 stk = [1] while nidx < N: if not stk: print(0) exit() cur = stk[-1] if lst[nidx] in links[cur]: stk.append(lst[nidx]) nidx += 1 else: stk.pop() print(1) 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25229 번역 번역 # 문제 # 방향이 없는 간선으로 이루어진 트리가 있으며, 각 노드는 정수 값을 가지고 있습니다. 인접한 두 노드의 값의 최대공약수(GCD)가 $1$보다 엄밀히 클 때, 이 두 노드를 **GCD-조화롭다(GCD-harmonic)**고 합니다.
📝 문제 정보 # 링크: 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/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/2132 🧐 관찰 및 접근 # 트리에서 특정 경로 위에서 노드들의 가중치의 합 트리의 경로란, 하나의 간선을 두번 지나지 않으며 $a_i \in V, (a_i, a_{i+1}) \in E$ 를 만족하는 집합 다시말해, 그냥 특정 간선을 두번 타지 않고 갈 수 있는 시점~종점의 길 어떻게 구할지 생각해보자 어떤 점 $a_0$에서 경로를 시작한다고 해보자. 그 다음에 갈 수 있는 점은 $a_0$의 자식중 한곳에만 갈 수 있다. 한 자식한테 들어간다면, 다시 나올수가 없기 때문에 그 자식을 $a_1$이라고 한다면, 마찬가지로 그 자식중 한곳에만 갈 수 있다. 어? 이거 DFS아닌가? DFS처럼 할 수 있는 것 같다. 그러면 자식중에 어디로 가야하는가? 물론 가장 열매를 많이 먹을 수 있는 곳으로! 💻 풀이 # 코드 (C++): int N; vector<int> links[10010]; int val[10010]; int dfs(int cur, int par){ int ret = 0; for(auto nxt: links[cur]){ if(nxt == par) continue; ret = max(ret, dfs(nxt, cur)); } return ret + val[cur]; } void solve(){ cin >> N; rep(i, 1, N+1) cin >> val[i]; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } int ans = 0, idx = 1; rep(i, 1, N+1){ int res = dfs(i, -1); if(res > ans){ ans = res; idx = i; } } cout << ans << ' '<< idx << '\n'; } 🔒 구현 코드 잠금