알파카컵 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;
}
}
레이팅 미적용