백준 24124 - 高速道路 (Highway) (C++)

문제

• 문제 링크

  
   BOJ 24124 - 高速道路 (Highway) 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
이 트리에서는, 간선 $e$가 정점 $u, v$를 이을 때 $weight_{uv}$와 $weight_{vu}$가 다를 수 있다.
어떤 $e$에 대해 번호가 작은 정점에서 큰 정점으로 향하는 방향을 상행, 반대를 하행이라고 하자.

이때, 다음 두 쿼리를 수행하는 프로그램을 작성해보자.



$I$ $r$ $s$ $t$ : $r$번 간선의 상행 소요 시간을 $s$, 하행 소요 시간을 $t$로 수정한다.

$Q$ $x$ $y$ : $x$번 정점에서 $y$번 정점에 도달하는 총 소요 시간을 출력한다.

• 제한

TL : $4$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10^5$

$1 ≤ Q ≤ 10^5$

$1 ≤ s, t ≤ 10^3$

최초 모든 간선의 상행, 하행 소요 시간은 모두 $1$이다.

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• heavy-light 분할 (heavy-light decomposition)
• 세그먼트 트리 (segtree)

풀이

트리에서 $point$ $update$ $range$ $query$를 처리해야 할 듯 하다.
이 문제를 선형 구조에서 푼다면 단순히 합 세그먼트 트리를 이용해 쉽게 처리할 수 있다.

이에 따라, 트리에서 선형적인 작업을 수행할 수 있게 해주는 $heavy$ $light$ $decompositon$으로 전처리 과정을 거치자.

하나 특별한 것이, 간선 하나에 대해 서로 다른 가중치가 존재할 수 있다는 점이다.

이는 루트 정점을 제외한 $n-1$개 정점들에 대해 해당 정점에서 위로 나올 때 가중치, 들어올 때 가중치를 각각 부여한다고 생각하면 쉽게 해결할 수 있다.

즉, 가중치가 두가지임에 따라 각각의 상태 관리를 담당할 두 개의 세그먼트 트리가 필요하다는 것이다.
전자의 상태를 $p(1)$, 후자의 상태를 $q(0)$라 하자.

---

간선의 방향성이 유의미하므로, $hld$에서 체인 단위로 끌어 올리며 쿼리를 날릴 때 유의해야 한다.

$x$에서 $y$로 이동하고 $l =$ $LCA(x, y)$라 하자.

앞서 정의한 두가지의 상태를 봤을 때,

$x$에서 $l$로 이동할 땐 $p$의 상태를 참고해야 한다.

$l$에서 $y$로 이동할 땐 $q$의 상태를 참고해야 한다.

어떤 간선에 대한 정점쌍을 다룰 때, 헷갈리지 않도록 적절한 일반성을 유지해야 할 것이다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
unordered_map <int, pair<int, int>> eg;
vector <int> Gr[N], tree[N];
int n, m;
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i(1); i < n; i++)
    {
        int u, v; cin >> u >> v;
        if (u > v) swap(u, v);
        Gr[u].push_back(v);
        Gr[v].push_back(u);
        eg[i] = { u, v };
    }
}
 
int dep[N], par[N], sz[N];
int cur, top[N], in[N];
void hldDFS(int now)
{
    sz[now] = 1;
    for (int& nxt : Gr[now])
        if (!sz[nxt])
        {
            dep[nxt] = dep[now] + 1;
            par[nxt] = now;
            hldDFS(nxt);
            sz[now] += sz[nxt];
            tree[now].push_back(nxt);
 
            if (sz[tree[now][0]] < sz[nxt])
                swap(tree[now][0], tree[now].back());
        }
}
void hldETT(int now)
{
    in[now] = ++cur;
    for (int& nxt : tree[now])
    {
        top[nxt] = nxt ^ tree[now][0] ? nxt : top[now];
        hldETT(nxt);
    }
}
 
vector <int> w_p(N, 1), w_q(N, 1);
int pseg[N], qseg[N];
void segUpdate(int i, int val1, int val2)
{
    while (i < N)
    {
        pseg[i] += val1;
        qseg[i] += val2;
        i += i & -i;
    }
}
int segQuery(int i, int op, int res = 0)
{
    auto& seg(op ? pseg : qseg);
    for (; i; i -= i & -i)
        res += seg[i];
    return res;
}
int getLCA(int x, int y)
{
    while (top[x] ^ top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = par[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
int hldQuery(int op, int x, int y, int res = 0)
{
    while (top[x] ^ top[y])
    {
        res += segQuery(in[x], op) - segQuery(in[top[x]] - 1, op);
        x = par[top[x]];
    }
    return res + segQuery(in[x], op) - segQuery(in[y], op);
}
void Query()
{
    for (char op; m--;)
    {
        cin >> op;
        if (op == 'I')
        {
            int r, s, t; cin >> r >> s >> t;
            auto [x, y](eg[r]);
            int v(dep[x] > dep[y] ? x : y);
 
            if (x ^ v) swap(s, t);
            segUpdate(in[v], s - w_p[v], t - w_q[v]);
            w_p[v] = s; w_q[v] = t;
        }
        else
        {
            int x, y; cin >> x >> y;
            int l(getLCA(x, y));
 
            cout << hldQuery(1, x, l) + hldQuery(0, y, l) << '\n';
        }
    }
}
int main()
{
    Input();
    hldDFS(1);
    hldETT(1);
    for (int i(1); i <= n; segUpdate(i++, 1, 1));
    Query();
}

comment

끝