제출 #1324336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324336		benjaminshih	Logičari (COCI21_logicari)	C++20	0 / 110	2 ms	440 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxn = 100010;
const int INF = 1e9;

vector<int> g[mxn];
int dp[mxn][4];
bool vis[mxn];

// U, V 用來儲存環上的那條邊 (Back-edge)
int n, U = -1, V = -1;

// 找環：在遍歷過程中若遇到已訪問過的點且非父親，則該邊為環邊
void find_cycle(int now, int par) {
    vis[now] = true;
    for (auto nxt : g[now]) {
        if (nxt == par) continue;
        if (vis[nxt]) {
            if (U == -1) { // 找到第一條回邊即可
                U = now;
                V = nxt;
            }
        } else {
            find_cycle(nxt, now);
        }
    }
}

// type: 用來指定斷開邊 (U, V) 的顏色假設
// type 0: U藍, V藍
// type 1: U藍, V紅
// type 2: U紅, V藍
// type 3: U紅, V紅
void dfs(int now, int par, int type) {
    ll sum0 = 0, sum1 = 0;
    bool possible0 = true, possible1 = true;

    for (auto nxt : g[now]) {
        if (nxt == par) continue;
        // 遇到被斷開的邊 (U, V) 則跳過，不當作子節點處理
        if ((now == U && nxt == V) || (now == V && nxt == U)) continue;

        dfs(nxt, now, type);

        // 統計子節點資訊
        if (dp[nxt][0] == INF) possible0 = false;
        if (dp[nxt][1] == INF) possible1 = false;
        sum0 += dp[nxt][0];
        sum1 += dp[nxt][1];
    }

    // --- 計算當前節點的 DP ---

    // 狀態 0: 自己紅, 子樹給 0 藍 (所有孩子都要是狀態 1: 紅且滿足)
    dp[now][0] = possible1 ? min((ll)INF, sum1) : INF;

    // 狀態 2: 自己藍, 子樹給 0 藍 (所有孩子都要是狀態 0: 紅且缺父, 被我滿足)
    // 這裡原本寫 sum1+1-sum1+sum0，直接用 sum0 + 1 比較安全
    dp[now][2] = possible0 ? min((ll)INF, sum0 + 1) : INF;

    // 狀態 1: 自己紅, 子樹給 1 藍 (選一個孩子是狀態 3[藍滿足], 其他是狀態 1[紅滿足])
    dp[now][1] = INF;
    if (possible1) {
        for (auto nxt : g[now]) {
            if (nxt == par) continue;
            if ((now == U && nxt == V) || (now == V && nxt == U)) continue;
            
            if (dp[nxt][3] != INF) {
                // 從 sum1 中扣除該孩子的 cost1，加上該孩子的 cost3
                ll cost = sum1 - dp[nxt][1] + dp[nxt][3];
                dp[now][1] = min((ll)dp[now][1], cost);
            }
        }
    }

    // 狀態 3: 自己藍, 子樹給 1 藍 (選一個孩子是狀態 2[藍缺父], 其他是狀態 0[紅缺父])
    dp[now][3] = INF;
    if (possible0) {
        for (auto nxt : g[now]) {
            if (nxt == par) continue;
            if ((now == U && nxt == V) || (now == V && nxt == U)) continue;

            if (dp[nxt][2] != INF) {
                // 從 sum0 中扣除該孩子的 cost0，加上該孩子的 cost2，自己是藍色所以 +1
                ll cost = sum0 - dp[nxt][0] + dp[nxt][2];
                dp[now][3] = min((ll)dp[now][3], cost + 1);
            }
        }
    }

    // --- 特殊處理：當遍歷到 V 時，根據假設強制修正狀態 ---
    // 因為 V 的鄰居 U 的顏色已經被 type 固定了，這會改變 V 對子樹的需求
    if (now == V) {
        int cost0 = dp[now][0];
        int cost1 = dp[now][1];
        int cost2 = dp[now][2];
        int cost3 = dp[now][3];

        // 重置為 INF，只保留合法的假設
        for(int k = 0; k < 4; k++) dp[now][k] = INF;

        // Type 0: U(藍), V(藍)。V 看到 U(藍)，已經滿足「看到1個藍」，
        // 所以 V 不需要從子樹拿藍色，且 V 自己是藍色。
        // 這對應於 Tree DP 中的狀態 2 (藍, 子樹0)，但在全域看來是 Satisfied (類似狀態 3 的功能)。
        // 父節點看 V 是「藍色且 Satisfied」，所以我們把原本的 cost2 填入 dp[now][3]。
        if (type == 0) dp[now][3] = cost2; 
        
        // Type 1: U(藍), V(紅)。V 看到 U(藍)，滿足。
        // V 是紅色，子樹提供 0。對應 cost0。全域看來是 Satisfied。
        // 父節點看 V 是「紅色且 Satisfied」，填入 dp[now][1]。
        if (type == 1) dp[now][1] = cost0;

        // Type 2: U(紅), V(藍)。V 看到 U(紅)，未滿足。
        // V 需要子樹提供 1 藍。對應 cost3。
        // 父節點看 V 是「藍色且 Satisfied」，填入 dp[now][3]。
        if (type == 2) dp[now][3] = cost3; 

        // Type 3: U(紅), V(紅)。V 看到 U(紅)，未滿足。
        // V 需要子樹提供 1 藍。對應 cost1。
        // 父節點看 V 是「紅色且 Satisfied」，填入 dp[now][1]。
        if (type == 3) dp[now][1] = cost1;
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    if (!(cin >> n)) return 0;

    for(int i = 0 ; i < n ; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    find_cycle(1, 0);

    int ans = INF;

    // Type 0: U=Blue, V=Blue
    // U 看到 V(Blue) 滿足，所以 U 需要子樹提供 0 藍 (dp[U][2])
    dfs(U, 0, 0);
    ans = min(ans, dp[U][2]);

    // Type 1: U=Blue, V=Red
    // U 看到 V(Red) 不滿足，所以 U 需要子樹提供 1 藍 (dp[U][3])
    dfs(U, 0, 1);
    ans = min(ans, dp[U][3]);

    // Type 2: U=Red, V=Blue
    // U 看到 V(Blue) 滿足，所以 U 需要子樹提供 0 藍 (dp[U][0])
    dfs(U, 0, 2);
    ans = min(ans, dp[U][0]);

    // Type 3: U=Red, V=Red
    // U 看到 V(Red) 不滿足，所以 U 需要子樹提供 1 藍 (dp[U][1])
    dfs(U, 0, 3);
    ans = min(ans, dp[U][1]);

    if(ans >= INF) cout << -1 << '\n';
    else cout << ans << '\n';
    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50