백준 28425 - 점수 계산하기 (C++)

문제

• 문제 링크

  
   BOJ 28425 - 점수 계산하기 
  

• 문제 요약

$r$ $v$ $:$ $r$번 노드가 루트일 때 $v$번 직원의 점수$?$


$N$개의 노드로 이루어진 트리와, 위 내용의 $Q$개의 쿼리가 주어진다.
각 쿼리에 맞는 답을 계산하여 출력하자.


• 제한

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




$1 ≤ N, Q ≤ 10^5$

$0 ≤ score ≤ 10^4$

알고리즘 분류

• 트리(trees)
• 다이나믹 프로그래밍(dp)
• 트리에서의 다이나믹 프로그래밍(dp_tree)
• 최소 공통 조상(lowest common ancestor)

풀이

쿼리 없이 루트 노드를 $1$로 잡고 정적인 상태에서의 답을 계산해보자.

이는 트리$DP$로 간단히 계산할 수 있다.

$dp[i] :$ $i$번 노드를 루트로 하는 서브 트리의 $Σscore$.

그러나 쿼리 내용에 의하면 루트가 계속적으로 바뀔 수 있다.
적당한 사이즈의 트리를 그려놓고 관찰 및 $case$_$work$를 해보면 되는데, 나는 다음의 $3$가지로 결론이 났다.

$r == v$ 면 답은 $dp[1]$.

$LCA(r, v) == v$ 즉, 상하관계가 역전 된다면 $?$

나머지 모든 경우는 여전히 $v$의 서브트리만이 남을테니 답은 $dp[v]$.

---

두번째 경우는 트리의 모양이 뒤집어진다.

바뀐 트리 기준에서 $v$의 부모는, $v→r$의 경로 상에 맨 처음 등장하는 정점$(k)$이 된다.
또한 기존 트리에서 $k$를 루트로 하는 서브 트리 외에 존재하는 모든 정점들이, $v$의 서브 트리에 포함되게 된다.

따라서 답은 $dp[1] - dp[k]$.

$k$는 $r$이 $v$와 깊이 차가 $1$이 될 때까지 끌어올린 정점과 같으므로, $LCA$를 찾을 때와 비슷하게 $Binary$ $Lifting$을 이용해주면 되겠다.

결과적으로 전처리 $O(NlogN)$, 쿼리당 $O(log^2N)$의 복잡도를 가지므로 문제를 $O(Qlog^2N)$에 풀 수 있다.

그 외 $Segment$ $Tree$ $+$ $ETT$를 이용한 풀이나, $Offline$ $Query$로 문제를 해결하는 등 다양한 풀이가 있는 듯 하다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <int> Gr[N];
int depth[N], table[N][18];
int n, q, dp[N];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i(1); i <= n; cin >> dp[i++]);
    for (int i, j, o{}; ++o < n;)
    {
        cin >> i >> j;
        Gr[i].push_back(j);
        Gr[j].push_back(i);
    }
}
void Init(int now, int dep)
{
    depth[now] = dep;
    for (int& next : Gr[now])
        if (!depth[next])
        {
            table[next][0] = now;
            Init(next, dep + 1);
            dp[now] += dp[next];
        }
}
void TableDP()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n; i++)
            table[i][j] = table[table[i][j - 1]][j - 1];
}
int lifting(int x, int diff)
{
    for (int i{}; diff; diff >>= 1, i++)
        if (diff & 1)
            x = table[x][i];
    return x;
}
int GetLCA(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
 
    x = lifting(x, depth[x] - depth[y]);
    if (x ^ y)
    {
        for (int i(17); !!~i; i--)
            if (table[x][i] ^ table[y][i])
            {
                x = table[x][i];
                y = table[y][i];
            }
        x = table[x][0];
    }
    return x;
}
void Query()
{
    for (int r, v; q--;)
    {
        cin >> r >> v;
        int lca(GetLCA(r, v));
 
        if (r == v) cout << dp[1] << '\n';
        else if (lca == v)
        {
            r = lifting(r, depth[r] - depth[lca] - 1);
            cout << dp[1] - dp[r] << '\n';
        }
        else cout << dp[v] << '\n';
    }
}
int main()
{
    Input();
    Init(1, 1);
    TableDP();
    Query();
}

comment

끝