철도 2 (Railway 2)

트리 구조에서 모든 노드 쌍 사이의 거리 함수 $f(i,j)$의 총합을 구하는 문제입니다. 이 문제의 핵심은 특정 노드에서 출발할 때 트리의 지름(Diameter) 끝점 중 하나로 향하는 경로가 최적의 해를 포함한다는 점입니다.

트리의 지름을 구한 뒤, 두 끝점을 기준으로 각 노드까지의 거리를 계산하여 정렬합니다. 이를 통해 각 노드별 기여도를 계산하여 최종 합계를 도출할 수 있습니다.

const int MAXN = 500005;
const int MOD = 1e9 + 7;

vector<pair<int, long long>> adj[MAXN];
long long dist_to_node[MAXN], max_dist[MAXN];
int farthest_point;

void find_farthest(int u, int p, long long d) {
    if (d > dist_to_node[farthest_point]) farthest_point = u;
    dist_to_node[u] = d;
    for (auto& [v, w] : adj[u]) {
        if (v != p) find_farthest(v, u, d + w);
    }
}

long long solve_railway(int n) {
    farthest_point = 1;
    dist_to_node[1] = 0;
    find_farthest(1, 0, 0);
    
    int u = farthest_point;
    dist_to_node[u] = 0;
    find_farthest(u, 0, 0);
    int v = farthest_point;
    
    for(int i=1; i<=n; ++i) max_dist[i] = dist_to_node[i];
    
    dist_to_node[v] = 0;
    find_farthest(v, 0, 0);
    for(int i=1; i<=n; ++i) max_dist[i] = max(max_dist[i], dist_to_node[i]);
    
    sort(max_dist + 1, max_dist + n + 1);
    long long total_sum = 0;
    for (int i = 1; i <= n; ++i) {
        total_sum = (total_sum + (max_dist[i] % MOD) * (n - i)) % MOD;
    }
    return (total_sum * 2) % MOD;
}

경찰과 도둑

추격 문제로, 경찰의 속도 $V1$과 도둑의 속도 $V2$의 관계에 따라 전략이 달라집니다. $V1 \leq V2$라면 도둑은 루트 방향에서 잡히게 되며, 그렇지 않다면 도둑이 도망갈 수 있는 최대 거리를 이분 탐색(Binary Search)으로 결정해야 합니다.

LCA(Lowest Common Ancestor)와 트리의 깊이를 활용하여 각 시점의 위치를 계산하고, 리프 노드 방향으로의 도주와 경로상에서의 체포 가능성을 비교 분석합니다.

섬 (Islands)

간선의 개수와 연결 상태의 특성을 이용하는 문제입니다. 인접한 노드 $(x-1, x+1)$을 연결하는 간선을 찾고, 이를 기준으로 BFS를 수행하여 유효한 채색(Coloring) 방식을 결정합니다.

점프 게임 (Jump Game)

거리가 $K$ 이상인 가중치들의 합을 최대화하는 문제입니다. 세그먼트 트리(Segment Tree)를 사용하여 $K$개의 상태를 유지하며 동적 계획법(DP)을 최적화합니다.

struct SegTree {
    struct Node {
        int left, right;
        long long max_val, lazy;
    } tree[MAXN * 64];
    int node_count = 1;

    void apply_tag(int p, long long v) {
        tree[p].max_val += v;
        tree[p].lazy += v;
    }

    void push_down(int p) {
        if (tree[p].lazy != 0) {
            if (!tree[p].left) tree[p].left = ++node_count;
            apply_tag(tree[p].left, tree[p].lazy);
            if (!tree[p].right) tree[p].right = ++node_count;
            apply_tag(tree[p].right, tree[p].lazy);
            tree[p].lazy = 0;
        }
    }

    void update_range(int &p, int l, int r, int ql, int qr, long long v) {
        if (ql > qr) return;
        if (!p) p = ++node_count;
        if (ql <= l && r <= qr) {
            apply_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) / 2;
        if (ql <= mid) update_range(tree[p].left, l, mid, ql, qr, v);
        if (qr > mid) update_range(tree[p].right, mid + 1, r, ql, qr, v);
        tree[p].max_val = max(tree[tree[p].left].max_val, tree[tree[p].right].max_val);
    }
};

바이러스 (Virus)

점 분할 트리(Centroid Decomposition)를 구축하고 각 점에서의 깊이 정보를 바탕으로 보조 그래프를 생성합니다. 이후 다익스트라(Dijkstra) 알고리즘을 적용하여 전염 시간을 계산합니다.

친구 (Friends)

물고기들이 멈추는 구간 $[l, r]$이 주어졌을 때, 구간 DP를 사용하여 답을 구합니다. $dp[l][r]$을 구간 $[l, r]$에서의 최댓값으로 정의하고, 구간 내의 최댓값 위치 $k$를 기준으로 분할하여 계산합니다.

$$dp_{l,r} = \max_{l \leq k \leq r} \{ dp_{l,k-1} + dp_{k+1,r} + \binom{s_{l,r,k}}{2} \}$$

사막 점렬 (Desert Point Sequence)

Tarjan 알고리즘을 사용하여 이중 연결 성분(Biconnected Components)을 추출합니다. 사이클에 포함되지 않은 간선들을 우선적으로 제거한 뒤, 사이클의 크기에 따라 탐욕법(Greedy)을 적용하여 정답을 구합니다. 점 이중 연결 성분과 간선 이중 연결 성분의 차이에 주의해야 합니다.

집합 분할 (Set Partition)

비트마스크 DP를 활용합니다. 특정 집합 $S$가 선택되었을 때, 그 부분집합들의 선택 조건을 만족하는지 확인하며 상태를 전이합니다.

색칠하기 (Coloring)

양 끝의 색상이 같은 겹치지 않는 구간들을 최대한 많이 선택하는 문제입니다. 다음으로 가능한 위치를 빠르게 찾기 위해 희소 테이블(Sparse Table)을 활용한 doubling(Binary Lifting) 기법으로 최적화를 수행합니다.

void preprocess_doubling(int n) {
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }
}

int query_intervals(int L, int R) {
    int count = 0;
    int current = R;
    for (int j = 19; j >= 0; --j) {
        if (jump[current][j] >= L) {
            current = jump[current][j];
            count += (1 << j);
        }
    }
    return count;
}

산요로원 (Mountain Path)

올바른 괄호 문자열 판단 로직을 그래프 확장의 관점으로 재해석합니다. 현재 위치에서 좌우로 확장 가능한 상태를 정의하고 SPFA 또는 다익스트라를 통해 최단 경로를 탐색합니다.

접두사와 접미사

$dp[i]$를 '접두사 $i$까지 고려했을 때 가능한 최대 접미사 길이'로 정의합니다. 각 쿼리마다 제한 조건에 맞는 구간을 이분 탐색으로 탐색하며 탐욕적으로 전이합니다.

커튼 치기 (Draw the Curtains)

버튼 조작과 수동 조작의 비용 관계가 단조성(Monotonicity)을 가짐을 이용합니다. 투 포인터(Two-pointers) 기법과 BIT(Binary Indexed Tree)를 결합하여 각 쿼리에 대한 최적의 분기점을 빠르게 계산합니다.