ZOJ 3527 Shinryaku! Kero Musume：樹 DP 處理環與基站選址

問題描述

N（≤ 1e5）個村莊，每村可建聖地獲信仰值 F_i。每村有唯一糾纏村 P_i（有向邊 i -> P_i）。若村 i 及 P_i 都建聖地，i 的信仰值變化 G_i（可負）。求最大總信仰值。

圖結構分析

• 每個節點出度為 1，構成「基環樹」（功能圖）：若干環，環上節點為根向外生長樹枝。
• 無環情況下為普通樹 DP：dp[u][0/1] 表示 u 不選/選的最大值。轉移：dp[u][0] += max(dp[v][0], dp[v][1])；dp[u][1] += max(dp[v][0], dp[v][1] + G_v)（注意 G 屬於子節點 v）。

環上處理

環上的節點相互影響，無法直接樹 DP。技巧：拓撲排序剪掉所有樹枝，剩下純環。對環上任一節點 u，分兩種情況 DP 兩次取最大：

• 情況 1：u 不選。設 dp[u][0]=0, dp[u][1]=-INF，對其樹枝跑樹 DP，累加子樹貢獻 max(dp[v][0], dp[v][1])。
• 情況 2：u 選。設 dp[u][0]=-INF, dp[u][1]=F_u，累加 max(dp[v][0], dp[v][1] + G_v)。
• 環上其餘節點同理，但需按環順序傳遞？實際上，環上每個節點只有一個父節點（環上前驅），可將環「剪開」在 u 處，視為以 u 為根的樹（忽略環上另一條邊），做上述兩次 DP 取大。對環上每個節點都這樣做會重複，但因環上節點無樹枝（已剪掉），只需對環上任一節點做兩次 DP 即可覆蓋環上所有選擇組合（因環上節點間只有相鄰影響，剪開後變鏈）。

代碼框架

// 拓撲排序刪除入度為0的節點（樹枝）
void topsort() {
    queue q;
    for(i=1..n) if(in[i]==0) q.push(i);
    while(!q.empty()) {
        int x=q.front(); q.pop(); vis[x]=1;
        for(int i=head[x];~i;i=e[i].next) {
            int to=e[i].to;
            if(--in[to]==0) q.push(to);
        }
    }
}
// 樹 DP
void dfs(int u, int fa) {
    dp[u][0]=0; dp[u][1]=a[u];
    for(int i=head[u];~i;i=e[i].next) {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += max(dp[v][0], dp[v][1] + e[i].val);
    }
}
// 環上節點 solve
ll solve(int u) {
    // 情況1：u不選
    dp[u][0]=0; dp[u][1]=-INF;
    ll ans1=0;
    for子樹v: dfs(v,u); ans1 += max(dp[v][0], dp[v][1]);
    // 情況2：u選
    dp[u][0]=-INF; dp[u][1]=a[u];
    ll ans2=0;
    for子樹v: dfs(v,u); ans2 += max(dp[v][0], dp[v][1] + e[i].val);
    return max(ans1, ans2);
}

複雜度

拓撲排序 O(N)，樹 DP 每節點處理一次，總 O(N)。完美支持 1e5。