P2607 [ZJOI2008] 骑士 （树形dp

#include 
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using ll = long long;
struct edge{
    int from,to,val;
    int next;
}g[2000010];
int head[2000010];
int fa[2000010];
ll h[2000010];
int vis[2000010];
ll dp[2000010][2];
int n,m;
int idx = 0;
int root = 0;
ll res = 0;
void add(int u, int v , int val){
    idx++;
    g[idx].from = u;
    g[idx].to = v;
    g[idx].val = val;
    g[idx].next = head[u];
    head[u] = idx;
}
 
void work(int x){
 
	vis[x] = 1;
	dp[x][0] =  0;
	dp[x][1] = h[x];
    for(int i = head[x] ; i ; i = g[i].next){
        int son = g[i].to;
        if(son == root){
            dp[son][1] = -1e9;   
            continue;
        }else{
            work(son);
            dp[x][1] += dp[son][0];
            dp[x][0] += max(dp[son][1] , dp[son][0]);
        }
    }
 
 
}
 
 
 
void findC(int u){
    vis[u] = 1;
    while(!vis[fa[u]]){
        u = fa[u];
        vis[u] = 1;
    }
    root = u ;
    work(u);
    ll tmp = max(dp[u][1] , dp[u][0]);
    u = fa[u];
    root = u;
    work(u);
    ll tmp2  = max(dp[u][1] , dp[u][0]);
    res += max(tmp , tmp2);
 
}
 
 
int main(){
    //memset(dp,0x3f,sizeof dp);
    cin>>n;
    for(int i = 1; i <= n ; i++){
        cin>>h[i]>>fa[i];
        add(fa[i] , i  , 0);
    }
 
    for(int i = 1 ; i <= n ; i++){
        if(!vis[i]){
            findC(i);
        }
 
    }
    cout<
 
}   
 
 
 

基环树  ，破环为链， 分别把两个点作为根 进行树dp

考虑到是森林，而不是单棵树， 所以每个点都要进行访问