알파카컵 1회: E - 알파카 여행 계획
플래티넘 IV의견: 0
알파카 왕국에는 \(N\)개의 목초지가 있다. 목초지는 \(1\)번부터 \(N\)번까지 번호가 붙어 있다.
목초지들은 \(N-1\)개의 길로 연결되어 있으며, 임의의 두 목초지 사이에는 정확히 하나의 단순 경로가 존재한다. 즉, 목초지와 길은 트리 구조를 이룬다.
각 길에는 이동할 때 드는 피로도 \(w\)가 있다.
알파카 원정대는 여러 개의 여행 계획을 세웠다. 하나의 여행 계획은 \(K\)개의 목초지 \(a_1, a_2, \dots , a_K\) 로 이루어진다. 원정대는 \(a_1\)에서 출발하여 \(a_2, a_3, \dots , a_K\)를 순서대로 방문한다.
각 여행 계획에 대해 다음 두 값을 구해야 한다.
- 원정대가 이동한 전체 피로도의 합
- 여행 중 지나간 길들 중 가장 큰 피로도
단, 같은 길을 여러 번 지나간다면 전체 피로도에는 지나간 횟수만큼 더한다.
- \(1 \le N \le 100000\)
- \(1 \le Q \le 100000\)
- \(1 \le u, v \le N\)
- \(1 \le w \le 1000000000\)
- \(1 \le K\), \(1 \le a_i \le N\)
- 모든 여행 계획에서 \(K\)의 총합 \(\le 300000\)
- 입력으로 주어지는 그래프는 항상 트리이다.
전체 피로도 합은 32비트 범위를 넘을 수 있으므로 64비트 정수를 사용해야 한다.
첫째 줄에 목초지의 개수 \(N\)과 여행 계획의 개수 \(Q\)가 주어진다.
다음 \(N-1\)개의 줄에 길의 정보 \(u\ v\ w\)가 주어진다. 이는 \(u\)번과 \(v\)번 목초지를 잇는 피로도 \(w\)인 길이 있다는 뜻이다.
그다음 \(Q\)개의 줄에 여행 계획이 \(K a_1 a_2 \dots a_K\) 형태로 주어진다.
각 여행 계획마다 한 줄에 두 정수 \(S\ M\)을 출력한다. \(S\)는 전체 이동 피로도의 합, \(M\)은 지나간 길 중 가장 큰 피로도이다.
단, 이동하지 않는 경우(\(K = 1\))에는 \(M = 0\)으로 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
서브태스크 1 | 10점 | \(1 \le N, Q \le 100\), \(\Sigma K \le 1000\) |
서브태스크 2 | 15점 | 트리가 일자 형태이다 (\(i\)번과 \(i+1\)번을 잇는다) |
서브태스크 3 | 20점 | 모든 여행 계획에서 \(K = 2\) |
서브태스크 4 | 20점 | 모든 간선의 피로도 \(w = 1\) |
서브태스크 5 | 35점 | 추가 제한 없음 |
5 3
1 2 3
2 3 5
2 4 1
4 5 7
3 3 5 1
2 1 1
4 5 3 4 124 7
0 0
23 7트리: 1-2(3), 2-3(5), 2-4(1), 4-5(7).
계획 1 (3→5→1): 3→5 경로는 3-2(5)-4(1)-5(7)=13, 5→1 경로는 5-4(7)-2(1)-1(3)=11. 합 24, 최대 간선 7.
계획 2 (1): 이동이 없으므로 0 0.
계획 3 (5→3→4→1): 5→3=13, 3→4=6, 4→1=4. 합 23, 최대 간선 7.
해설
알파카컵 1회: E - 알파카 여행 계획
알파카컵 1회: E - 알파카 여행 계획
1. 문제 요약
트리 위에서 \(Q\)개의 여행 계획(쿼리)이 주어집니다. 각 계획은 \(K\)개의 정점 방문 순서 \(A_1, A_2, \dots, A_K\)로 이루어져 있으며, 인접한 정점들을 최단 경로로 연속해서 이동할 때 다음 두 가지 값을 구해야 합니다.
- \(S\): 이동한 모든 간선의 피로도(가중치) 총합
- \(MX\): 이동한 모든 간선 중 가장 큰 단일 피로도
2. [서브태스크 1]: \(1 \le N, Q \le 100\), \(\sum K \le 1,000\)
\(N\)과 \(Q\)가 최대 100으로 매우 작고, 모든 쿼리의 \(K\)를 더한 값도 1,000밖에 되지 않는 조건입니다. 트리에서 두 정점을 잇는 단순 경로는 유일하므로, 복잡한 알고리즘 없이 매번 직접 경로를 찾아도 시간 내에 통과할 수 있습니다.
-
풀이: 각 쿼리마다 인접한 두 정점 \((A_i, A_{i+1})\) 쌍에 대해 DFS 또는 BFS를 가동하여 이동 경로를 직접 추적합니다. 탐색 과정에서 만나는 간선들의 가중치를 s에 누적하고, 그중 최댓값을 mx에 갱신합니다.
-
시간 복잡도: 한 번의 탐색에 \(O(N)\)이 걸리므로 쿼리당 \(O(K \cdot N)\)입니다. 전체 시간 복잡도는 \(O(\sum K \cdot N)\)이 되며, 최대 연산 횟수는 \(1,000 \times 100 = 10^5\)번으로 매우 여유롭게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, q;
vector<pll> v[101];
bool visited[101];
ll target, path_sum, path_max;
bool found;
void dfs_sub1(ll x, ll sum, ll mx) {
if (x == target) {
path_sum = sum;
path_max = mx;
found = true;
return;
}
visited[x] = true;
for (auto e : v[x]) {
ll next = e.first, weight = e.second;
if (!visited[next] && !found) {
dfs_sub1(next, sum + e.second, max(mx, e.second));
}
}
}
int main() {
fastio
cin >> n >> q;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
while (q--) {
ll k, a[1001];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
ll ans_s = 0, ans_mx = 0;
for (ll i = 1; i < k; i++) {
ll start_node = a[i];
target = a[i + 1];
fill(visited + 1, visited + n + 1, false);
found = false;
path_sum = 0;
path_max = 0;
dfs_sub1(start_node, 0, 0);
ans_s += path_sum;
ans_mx = max(ans_mx, path_max);
}
cout << ans_s << sp << ans_mx << endl;
}
return 0;
}
3. [서브태스크 2]: 트리가 일자 형태 (\(i\)번과 \(i+1\)번을 잇는다)
트리가 분기점 없이 \(1 - 2 - 3 - \dots - N\) 형태로 길게 늘어선 일자 정형인 경우입니다. 이 조건에서는 트리가 아니라 1차원 배열에서의 구간 쿼리 문제로 재해석할 수 있습니다.
-
풀이: \(i\)번 노드와 \(i+1\)번 노드를 연결하는 간선의 가중치를 배열의 \(i\)번째 원소로 둡니다. 두 정점 \(U\)와 \(V\) 사이를 이동할 때, 가중치의 합(\(S\))은 구간 합이 되고, 최대 가중치(\(MX\))는 구간의 최댓값이 됩니다. 구간 합과 간 최댓값을 세그먼트 트리를 구축하여 \(O(\log N)\)에 구합니다.
-
시간 복잡도: 전처리에 \(O(N \log N)\), 각 쿼리 처리에 \(O(K \log N)\)이 소요됩니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct T {
ll sum, max;
};
ll n, q, t = 1;
T tree[400001];
ll edges[100001];
void update(ll x) {
while (x > 1) {
x = d2(x);
tree[x].sum = tree[m2(x)].sum + tree[m2(x) + 1].sum;
tree[x].max = max(tree[m2(x)].max, tree[m2(x) + 1].max);
}
}
pll query(ll l, ll r, ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
return {tree[x].sum, tree[x].max};
} else if (r < ql || l > qr) {
return {0, 0};
} else {
ll mid = (l + r) / 2;
pll left_res = query(l, mid, ql, qr, m2(x));
pll right_res = query(mid + 1, r, ql, qr, m2(x) + 1);
return {left_res.first + right_res.first, max(left_res.second, right_res.second)};
}
}
int main() {
fastio
cin >> n >> q;
while (t < n) t *= 2;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
edges[a] = c;
}
for (ll i = 1; i < n; i++) {
tree[t + i - 1] = {edges[i], edges[i]};
}
for (ll i = t - 1; i >= 1; i--) {
tree[i].sum = tree[m2(i)].sum + tree[m2(i) + 1].sum;
tree[i].max = max(tree[m2(i)].max, tree[m2(i) + 1].max);
}
while (q--) {
ll k, a[300001];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
ll s = 0, mx = 0;
for (ll i = 1; i < k; i++) {
if (a[i] == a[i + 1]) continue;
ll u = a[i], v = a[i + 1];
if (u > v) swap(u, v);
pll res = query(1, t, u, v - 1, 1);
s += res.first;
mx = max(mx, res.second);
}
cout << s << sp << mx << endl;
}
return 0;
}
4. [서브태스크 3]: 모든 여행 계획에서 \(K = 2\)
방문해야 하는 정점이 오직 두 개(\(A_1, A_2\))인 경우입니다. 즉, 여러 정점을 거칠 필요 없이 단순히 트리 위의 한 쌍의 노드에 대해서만 경로 상의 합과 최댓값을 구하면 됩니다.여기서부터 일반적인 트리 구조에서 두 정점 사이의 경로를 효율적으로 처리하는 핵심 개념인 LCA(최소 공통 조상)가 필요합니다.
-
풀이: 트리에서 두 노드 \(U\)와 \(V\) 사이의 유일한 경로는 조상 노드인 \(\text{LCA}(U, V)\)를 정점으로 하여 꺾이는 구조를 가집니다. 따라서 \(U\)에서 조상까지 올라가는 법, \(V\)에서 조상까지 올라가는 법을 알면 문제를 풀 수 있습니다. 노드를 한 칸씩 부모로 올리면 서브태스크 1과 다를 바 없으므로, \(2^j\)칸씩 뛰어넘는 이진 탐색 기법을 사용해 조상을 \(O(\log N)\)만에 찾아냅니다.
-
시간 복잡도: 희소 배열 전처리 \(O(N \log N)\), 쿼리당 \(O(\log N)\)에 해결됩니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct T {
ll x, sum, max_val;
};
ll n, q, depth[100001];
pll parent[100001];
T dt[100001][21];
bool visited[100001];
vector<pll> v[100001];
void dfs(ll x) {
visited[x] = true;
for (auto e : v[x]) {
if (visited[e.first]) continue;
parent[e.first] = {x, e.second};
depth[e.first] = depth[x] + 1;
dfs(e.first);
}
}
pll lca(ll a, ll b) {
ll s = 0, mx = 0;
if (depth[a] < depth[b]) swap(a, b);
ll diff = depth[a] - depth[b];
for (ll i = 20; i >= 0; i--) {
if ((diff >> i) & 1) {
s += dt[a][i].sum;
mx = max(mx, dt[a][i].max_val);
a = dt[a][i].x;
}
}
if (a == b) return {s, mx};
for (ll i = 20; i >= 0; i--) {
if (dt[a][i].x != dt[b][i].x) {
s += dt[a][i].sum + dt[b][i].sum;
mx = max({mx, dt[a][i].max_val, dt[b][i].max_val});
a = dt[a][i].x;
b = dt[b][i].x;
}
}
s += dt[a][0].sum + dt[b][0].sum;
mx = max({mx, dt[a][0].max_val, dt[b][0].max_val});
return {s, mx};
}
int main() {
fastio
cin >> n >> q;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
depth[1] = 1;
dfs(1);
parent[1] = {1, 0};
for (ll i = 1; i <= n; i++) {
dt[i][0] = {parent[i].first, parent[i].second, parent[i].second};
}
for (ll j = 1; j <= 20; j++) {
for (ll i = 1; i <= n; i++) {
ll mid = dt[i][j - 1].x;
dt[i][j].x = dt[mid][j - 1].x;
dt[i][j].sum = dt[i][j - 1].sum + dt[mid][j - 1].sum;
dt[i][j].max_val = max(dt[i][j - 1].max_val, dt[mid][j - 1].max_val);
}
}
while (q--) {
ll k, a[5];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
if (a[1] == a[2]) {
cout << 0 << sp << 0 << endl;
} else {
pll res = lca(a[1], a[2]);
cout << res.first << sp << res.second << endl;
}
}
return 0;
}
5. [서브태스크 4]: 모든 간선의 피로도 \(w = 1\)
모든 간선의 가중치가 1인 가중치 없는 트리 상태입니다.
-
풀이: 간선의 가중치가 모두 1이므로, 두 노드 사이의 거리(가중치 합 \(S\))는 단순히 거쳐 가는 간선의 개수와 같습니다. 이는 각 노드의 루트로부터의 깊이 정보와 LCA를 이용해 공식으로 완벽하게 상수 시간에 구할 수 있습니다.$$ \text{Distance}(U, V) = \text{depth}[U] + \text{depth}[V] - 2 \times \text{depth}[\text{LCA}(U, V)] $$또한, 이동 경로에 간선이 하나라도 존재한다면 그 경로의 최대 피로도(\(MX\))는 무조건 1이 되며, 출발지와 목적지가 같아 이동하지 않는 경우에만 0이 됩니다.
-
시간 복잡도: 희소 배열을 통해 LCA를 \(O(\log N)\)에 구하므로, 쿼리당 \(O(K \log N)\)이 소요됩니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, q, depth[100001];
ll parent[100001];
ll dt[100001][21];
bool visited[100001];
vector<ll> v[100001];
void dfs(ll x) {
visited[x] = true;
for (auto e : v[x]) {
if (visited[e]) continue;
parent[e] = x;
depth[e] = depth[x] + 1;
dfs(e);
}
}
ll lca(ll a, ll b) {
if (depth[a] < depth[b]) swap(a, b);
ll diff = depth[a] - depth[b];
for (ll i = 20; i >= 0; i--) {
if ((diff >> i) & 1) {
a = dt[a][i];
}
}
if (a == b) return a;
for (ll i = 20; i >= 0; i--) {
if (dt[a][i] != dt[b][i]) {
a = dt[a][i];
b = dt[b][i];
}
}
return dt[a][0];
}
int main() {
fastio
cin >> n >> q;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
v[a].push_back(b);
v[b].push_back(a);
}
depth[1] = 1;
dfs(1);
parent[1] = 1;
for (ll i = 1; i <= n; i++) {
dt[i][0] = parent[i];
}
for (ll j = 1; j <= 20; j++) {
for (ll i = 1; i <= n; i++) {
dt[i][j] = dt[dt[i][j - 1]][j - 1];
}
}
while (q--) {
ll k, a[300001];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
ll total_s = 0, total_mx = 0;
for (ll i = 1; i < k; i++) {
if (a[i] == a[i + 1]) continue;
ll lca_node = lca(a[i], a[i + 1]);
ll dist = depth[a[i]] + depth[a[i + 1]] - m2(depth[lca_node]);
total_s += dist;
if (dist > 0) total_mx = max(total_mx, 1LL);
}
cout << total_s << sp << total_mx << endl;
}
return 0;
}
6. 정해
정해 풀이 1: 반복문 기반 이진 탐색
-
풀이: 서브태스크 3의 '희소 배열 점프 기법'을 임의의 \(K\)개 정점 배열로 확장한 정해입니다. 희소 배열의 원소를 조상 노드 번호(x), 가중치 합(sum), 최대 가중치(max)를 갖는 구조체로 설계합니다. 편향 트리 구조에서 하향식 재귀를 사용하면 스택 오버플로우나 TLE가 발생하므로, 반드시 1차 조상부터 20차 조상까지 반복문을 통해 바텀업(Bottom-Up) 방식으로 테이블을 채워야 합니다. 쿼리가 들어오면 인접한 노드쌍들을 순회하며 이진 탐색 조상 점프를 통해 합과 최댓값을 독립적으로 갱신합니다.
-
시간 복잡도: 희소 배열 전처리에 \(O(N \log N)\), 전체 쿼리 처리에 \(O(\sum K \log N)\)이 소요되어 가장 빠르고 안정적입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct T {
ll x, sum, max;
};
ll n, q, depth[100001];
pll parent[100001];
T dt[100001][21];
bool visited[100001];
vector<pll> v[100001];
void dfs(ll x) {
visited[x] = true;
for (auto e : v[x]) {
if (visited[e.first]) continue;
parent[e.first] = {x, e.second};
depth[e.first] = depth[x] + 1;
dfs(e.first);
}
}
pll lca(ll a, ll b) {
ll s = 0, mx = 0;
if (depth[a] < depth[b]) swap(a, b);
ll diff = depth[a] - depth[b];
for (ll i = 20; i >= 0; i--) {
if ((diff >> i) & 1) {
s += dt[a][i].sum;
mx = max(mx, dt[a][i].max);
a = dt[a][i].x;
}
}
if (a == b) return {s, mx};
for (ll i = 20; i >= 0; i--) {
if (dt[a][i].x != dt[b][i].x) {
s += dt[a][i].sum + dt[b][i].sum;
mx = max({mx, dt[a][i].max, dt[b][i].max});
a = dt[a][i].x;
b = dt[b][i].x;
}
}
s += dt[a][0].sum + dt[b][0].sum;
mx = max({mx, dt[a][0].max, dt[b][0].max});
return {s, mx};
}
int main() {
fastio
cin >> n >> q;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
dfs(1);
parent[1] = {1, 0};
for (ll i = 1; i <= n; i++) {
dt[i][0] = {parent[i].first, parent[i].second, parent[i].second};
}
for (ll j = 1; j <= 20; j++) {
for (ll i = 1; i <= n; i++) {
ll mid = dt[i][j - 1].x;
dt[i][j].x = dt[mid][j - 1].x;
dt[i][j].sum = dt[i][j - 1].sum + dt[mid][j - 1].sum;
dt[i][j].max = max(dt[i][j - 1].max, dt[mid][j - 1].max);
}
}
while (q--) {
ll k, s = 0, mx = 0, a[300001];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
for (ll i = 1; i < k; i++) {
pll res = lca(a[i], a[i + 1]);
s += res.first;
mx = max(mx, res.second);
}
cout << s << sp << mx << endl;
}
}
정해 풀이 2: Heavy-Light Decomposition (HLD) + 세그먼트 트리
-
풀이: 트리를 무거운 간선 중심의 여러 선형 체인(Chain)으로 분해하여 일렬로 편 뒤 세그먼트 트리로 관리하는 정해입니다. 간선 정보를 자식 노드의 인덱스(in_idx)에 귀속시킨 후, 구간 합과 구간 최댓값을 동시에 관리하는 세그먼트 트리를 빌드합니다. 두 노드 간의 경로를 구할 때는 두 노드가 같은 체인에 속할 때까지 체인을 건너뛰며 세그먼트 트리 쿼리를 합산·갱신합니다. 마지막에 같은 체인에 도달했을 때, LCA 정점 자체는 'LCA와 그 부모를 잇는 간선'의 가중치를 담고 있으므로 쿼리 구간에서 제외하는 세밀한 인덱스 처리가 핵심입니다. (이 풀이는 간선 가중치가 도중에 계속 바뀌는 업데이트 쿼리가 추가되어도 처리가 가능한 확장성을 가집니다.)
-
시간 복잡도: HLD 분해 및 트리 빌드 전처리에 \(O(N)\), 각 체인을 건너뛰며 세그먼트 트리를 탐색하므로 전체 쿼리 처리 복잡도는 \(O(\sum K \log^2 N)\)이 되어 제한 시간 내에 여유롭게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct T {
ll x, sum, max;
};
ll n, q, depth[100001];
pll parent[100001];
T dt[100001][21];
bool visited[100001];
vector<pll> v[100001];
void dfs(ll x) {
visited[x] = true;
for (auto e : v[x]) {
if (visited[e.first]) continue;
parent[e.first] = {x, e.second};
depth[e.first] = depth[x] + 1;
dfs(e.first);
}
}
pll lca(ll a, ll b) {
ll s = 0, mx = 0;
if (depth[a] < depth[b]) swap(a, b);
ll diff = depth[a] - depth[b];
for (ll i = 20; i >= 0; i--) {
if ((diff >> i) & 1) {
s += dt[a][i].sum;
mx = max(mx, dt[a][i].max);
a = dt[a][i].x;
}
}
if (a == b) return {s, mx};
for (ll i = 20; i >= 0; i--) {
if (dt[a][i].x != dt[b][i].x) {
s += dt[a][i].sum + dt[b][i].sum;
mx = max({mx, dt[a][i].max, dt[b][i].max});
a = dt[a][i].x;
b = dt[b][i].x;
}
}
s += dt[a][0].sum + dt[b][0].sum;
mx = max({mx, dt[a][0].max, dt[b][0].max});
return {s, mx};
}
int main() {
fastio
cin >> n >> q;
for (ll i = 1; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
dfs(1);
parent[1] = {1, 0};
for (ll i = 1; i <= n; i++) {
dt[i][0] = {parent[i].first, parent[i].second, parent[i].second};
}
for (ll j = 1; j <= 20; j++) {
for (ll i = 1; i <= n; i++) {
ll mid = dt[i][j - 1].x;
dt[i][j].x = dt[mid][j - 1].x;
dt[i][j].sum = dt[i][j - 1].sum + dt[mid][j - 1].sum;
dt[i][j].max = max(dt[i][j - 1].max, dt[mid][j - 1].max);
}
}
while (q--) {
ll k, s = 0, mx = 0, a[300001];
cin >> k;
for (ll i = 1; i <= k; i++) {
cin >> a[i];
}
for (ll i = 1; i < k; i++) {
pll res = lca(a[i], a[i + 1]);
s += res.first;
mx = max(mx, res.second);
}
cout << s << sp << mx << endl;
}
}
평가 및 의견
알파카컵 1회: E - 알파카 여행 계획
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카컵 1회: E - 알파카 여행 계획