Tree

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

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