洛谷P2607 [ZJOI2008]騎士(樹形dp)

題目描述

Z國的騎士團是一個很有勢力的組織，幫會中匯聚了來自各地的精英。他們劫富濟貧，懲惡揚善，受到社會各界的贊揚。

最近發生了一件可怕的事情，邪惡的Y國發動了一場針對Z國的侵略戰爭。戰火綿延五百裡，在和平環境中安逸了數百年的Z國又怎能抵擋的住Y國的軍隊。於是人們把所有的希望都寄托在了騎士團的身上，就像期待有一個真龍天子的降生，帶領正義打敗邪惡。

騎士團是肯定具有打敗邪惡勢力的能力的，但是騎士們互相之間往往有一些矛盾。每個騎士都有且僅有一個自己最厭惡的騎士（當然不是他自己），他是絕對不會與自己最厭惡的人一同出征的。

戰火綿延，人民生靈塗炭，組織起一個騎士軍團加入戰鬥刻不容緩！國王交給了你一個艱巨的任務，從所有的騎士中選出一個騎士軍團，使得軍團內沒有矛盾的兩人（不存在一個騎士與他最痛恨的人一同被選入騎士軍團的情況），並且，使得這支騎士軍團最具有戰鬥力。

為了描述戰鬥力，我們將騎士按照1至N編號，給每名騎士一個戰鬥力的估計，一個軍團的戰鬥力為所有騎士的戰鬥力總和。

輸入輸出格式

輸入格式：

輸入文件knight.in第一行包含一個正整數N，描述騎士團的人數。

接下來N行，每行兩個正整數，按順序描述每一名騎士的戰鬥力和他最痛恨的騎士。

輸出格式：

輸出文件knight.out應包含一行，包含一個整數，表示你所選出的騎士軍團的戰鬥力。

輸入輸出樣例

3
10 2
20 3
30 1

30

說明

對於30%的測試數據，滿足N ≤ 10；

對於60%的測試數據，滿足N ≤ 100；

對於80%的測試數據，滿足N ≤ 10 000。

對於100%的測試數據，滿足N ≤ 1 000 000，每名騎士的戰鬥力都是不大於 1 000 000的正整數。

看到標簽是樹形DP就點進來了

可沒想到這題給了一個圖？？

不過冷靜下來，我們不難發現，這張圖實際上只有一個環，也就是傳說中的基環樹

因此我們按照套路，把一條環上的邊破壞掉，然後對兩棵獨立的樹做樹形DP

設$f[i][0/1]$表示該節點是否選擇時的最大價值

轉移的時候枚舉孩子是否選擇

不過在BZOJ上死活RE

// luogu-judger-enable-o2
#include<cstdio>
#include<vector>
#include<cstring>
#define LL long long 
#define Pair pair<int,int>
using namespace std;
const int MAXN=3*1e6+10;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
char buf[1<<22],*p1=buf,*p2=buf;
inline int read() {
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct Edge {
    int u, v, nxt;
}edge[MAXN];
int head[MAXN], num=0;
void AddEdge(int x,int y) {
    edge[num] = (Edge){x, y, head[x]};
    head[x] = num++;
} 
int val[MAXN], vis[MAXN], BeginEdge;
LL f[MAXN][2];
Pair Begin;
void FindCircle(int now,int fa) {
    vis[now] = 1;
    for(int i = head[now];i != -1;i = edge[i].nxt) {
        if( (i ^ 1) == fa) continue;
        if(vis[ edge[i].v ]) {BeginEdge = i;Begin.first = now;Begin.second = edge[i].v;continue ;}
        FindCircle(edge[i].v, i);
    }
}
LL Dp(int now,int fa) {
    f[now][0] = 0;
    f[now][1] = val[now];
    for(int i = head[now];i != -1;i = edge[i].nxt) {
        if((i ^ 1) == fa) continue;
        if((i == BeginEdge) || ((i ^ 1) == BeginEdge)) continue;
        Dp(edge[i].v, i);
        f[now][0] += max(f[edge[i].v][1], f[edge[i].v][0]);
        f[now][1] += f[edge[i].v][0];
    }
    return f[now][0];
}
int main() {
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    int N = read();
    memset(head, -1, sizeof(int) * N *4);
    for(register int i=1;i<=N;i++) {
        val[i] = read();
        int x = read();
        AddEdge(i,x),AddEdge(x,i);
    }
    long long  ans = 0;
    for(register int i=1;i<=N;i++) {
        if(!vis[i]) {
            FindCircle(i,-2);
            ans += max(Dp(Begin.first,-1),Dp(Begin.second,-1));
        }
    }
    printf("%lld", ans);
    return 0;
}