[18770] 불안정한 물질

난이도: Platinum II

 

태그

• Functional Graph
• Dynamic Programming
  • on Tree (트리 DP)
  • on Cycle (원형 DP)
    // 이거 정식 명칭이 뭐지
• Cycle Detection → Tortoise and Hare
• Depth-First Search

 

풀이

1. 문제 상황을 요약해보자.

Functional Graph가 주어질 때, 정점들을 적절히 선택해서 점수 (선택한 정점들에 적힌 수의 합)를 최대화해야 하는 문제입니다.

이 때, 인접한 두 정점을 동시에 선택할 수는 없습니다.

 

2. Functional Graph가 아니라 Tree였다면?

잘 알려진 Tree DP 문제가 됩니다. "/<2533> 사회망 서비스(SNS)" 와 비슷한 문제가 되죠.

 

풀이를 적자면, 아래와 같습니다.

\( dp_{v, c} \) = 정점 \( v \)를 루트로 하는 서브트리에서, \( v \)번 정점의 선택 여부를 \( c \)라고 할 때 얻을 수 있는 점수의 최대 라고 합시다.

 

초항은 리프노드 \( l \)들에 대해, \( dp_{v, 0} = 0 \), \( dp_{v, 1} = A_{v} \)입니다.

점화식은 \( c = 0 \)이랑 \( c = 1 \)로 나눠서 구하면 됩니다.

• \( c = 0 \): \( v \)의 자식 \( w \)의 서브트리에 대한 최대 점수를 구하면 됩니다.
  \( dp_{v, 0} = \sum\limits_{w \in \text{chlid}(v)} \max(dp_{w, 0}, dp_{w, 1}) \)
• \( c = 1 \): \( v \)의 자식 \( w \)의 서브트리에 대해, \( w \)를 선택하지 않는 최대 점수를 구하면 됩니다.
  그 뒤에는 \( A_{v} \)를 선택해서 얻는 점수도 추가해야겠죠.
  \( dp_{v, 0} = A_{v} + \sum\limits_{w \in \text{chlid}(v)} dp_{w, 0} \)

 

3. Functional Graph가 아니라 Cycle이었다면?

잘 알려진 Cycle DP 문제가 됩니다. "/<2482> 색상환" 과 비슷한 문제가 되죠.

 

풀이를 적자면, 아래와 같습니다.

사이클에 있는 정점을 각각 \( v_1, v_2, \ldots, v_n \)이라고 해봅시다.

그러고, \( dp_{i, s, t} \) = 첫 \( i \)개의 정점을 이 순서대로 선형으로만 나열했을 때, \( v_1 \)번 정점의 선택 여부를 \( s \)라 하고 \( v_i \)번 정점의 선택 여부를 \( t \)라 할 때 얻을 수 있는 점수의 최대 를 정의해봅시다.

 

문제의 답은, \( \max(dp_{n, 0, 0}, dp_{n, 0, 1}, dp_{n, 1, 0}) \)이 됩니다.

// \( dp_{n, 1, 1} \)은 \( v_1 \)과 \( v_n \)이 동시에 선택되었다는 의미이니 불가능하죠.

예외적으로 \( n = 1 \)일 때는 \( dp_{n, 1, 1} \)도 포함시켜야 하지만요.

 

초항은, \( dp_{1, 0, 0} = 0 \)과 \( dp_{1, 1, 1} = A_{v_1} \)이 됩니다.

그럼, 이제 선형으로 나열된 문제를 푸는 것이니 점화식은 아래와 같이 나타낼 수 있습니다.

• \( dp_{i, c, 0} \)은, \( i-1 \)번째 정점의 선택 여부와 상관없으므로 \( \max(dp_{i-1, c, 1}, dp_{i-1, c, 0}) \)이 됩니다.
• \( dp_{i, c, 1} \)은, \( i-1 \)번째 정점을 선택하지 말아야 하므로, \( dp_{i-1, c, 0} + A_{v_i} \)가 됩니다.

 

4. 그럼, Functional Graph를 Cycle + 이에 연결된 Tree들 로 표현한다면?

그러니까, 아래와 같은 그림의 느낌으로 나눠봅시다.

사이클 하나랑 트리 여러 개.

각각의 트리는 이미 [2]에서 다뤘습니다. 계산의 편의를 위해, 각 트리의 루프는 사이클에 올라와있는 정점으로 해봅시다.

 

위 그림을 보면 알겠지만, 사이클을 무시하고 트리만 보면, 트리끼리는 서로 독립적입니다.

그러니, \( 3 \)번 정점과 이의 서브트리에서 무슨 짓을 하든 \( 4 \)번 정점과는 관련없다는 소리죠.

// 물론 실제로는 사이클 때문에 관련이 있지만, 사이클을 무시한다면 관련이 없다는 의미입니다.

 

그럼, 각각의 트리에 대해 답을 구한 뒤, 이를 사이클 위의 정점으로 모아보는 건 어떨까요?

즉, 사이클 위의 각 정점에 쓰인 값을 \( A_{v} \)로 하고 점수의 합을 구하는 대신,

사이클 위의 정점들에 대해 이 정점을 선택한다면 \( dp_{v, 1} \)점을, 선택하지 않는다면 \( dp_{v, 0} \)점을 얻는다고 한다면?

 

남은 건 사이클에 대한 처리 뿐이고, 이건 [3]에서 다룬 부분이 됩니다.

다만, 이번에는 선택하지 않았을 때 추가되는 값도 점화식에서 고려해줘야겠죠.

 

코드

const ll INF = 1e18;
int ptr[100020]; vector<int> adj[100020];
ll arr[100020];
 
bool chk[100020];
 
ll dp[2][100020];
void dpf(int now){
    //cout << "DPF " << now << endl << flush;
    dp[0][now] = 0; dp[1][now] = arr[now];
    chk[now] = 1;
    for (int nxt : adj[now]){
        if (chk[nxt]){ continue; }
        dpf(nxt);
        dp[0][now] += max(dp[0][nxt], dp[1][nxt]);
        dp[1][now] += dp[0][nxt];
    }
}
 
ll ans = 0;
void f(int now){
    int v = ptr[now], w = ptr[ ptr[now] ];
    while (v != w){ v = ptr[v]; w = ptr[ ptr[w] ]; }
    vector<int> pos;
    int p = v; while (!chk[p]){ chk[p] = 1; pos.push_back(p); p = ptr[p]; }
    for (int p : pos){ /*cout << "CALL ";*/ dpf(p);  }
    int k = pos.size();
    if (k == 1){ ans += max(dp[0][p], dp[1][p]); }
    else{
        vector<pl4> dp2(k);
        dp2[0].fr.fr = dp[0][p]; dp2[0].sc.sc = dp[1][p];
        dp2[0].fr.sc = dp2[0].sc.fr = -INF;
        for (int i = 1; i < k; i++){
            int p = pos[i];
            dp2[i].fr.fr = max(dp2[i-1].fr.fr, dp2[i-1].fr.sc) + dp[0][p];
            dp2[i].fr.sc = dp2[i-1].fr.fr + dp[1][p];
            dp2[i].sc.fr = max(dp2[i-1].sc.fr, dp2[i-1].sc.sc) + dp[0][p];
            dp2[i].sc.sc = dp2[i-1].sc.fr + dp[1][p];
        }
        ans += max({dp2[k-1].fr.fr, dp2[k-1].fr.sc, dp2[k-1].sc.fr});
    }
}
 
void Main(){
    int t; cin >> t; while (t--){
        int n; cin >> n;
        for (int i = 1; i <= n; i++){
            cin >> arr[i] >> ptr[i];
            adj[ ptr[i] ].push_back(i);
        }
        ans = 0;
        for (int i = 1; i <= n; i++){
            if (chk[i]){ continue; }
            f(i);
        }
        cout << ans << endl;
        for (int i = 1; i <= n; i++){ adj[i].clear(); chk[i] = 0; }
    }
}