基环树

1584：骑士

每个骑士都有讨厌的对象，构成一个环，求最大值（能取的最大战斗力）

#include<queue>
#include<iostream>
#include<algorithm> 
typedef long long LL;
#define INF 1e9
using namespace std;
const int maxn=1e6+10;
int n,head[maxn],w[maxn],idx;
LL f[maxn][2],sum;
int r1,r2,vis[maxn];
struct node{
	int to,nex;
}e[maxn];
void adde(int x,int y){  //单向边 
	e[++idx]={y,head[x]}; 
	head[x]=idx;
}
void findd(int x,int rt){  //找出两个根 
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nex){
		int v=e[i].to;
		if(v==rt) {
			r1=x;r2=v;
			return;
		}
		if(vis[v]) continue;
		findd(v,rt);
	}
}

LL dfs(int u,int rt){
	f[u][0]=0;f[u][1]=w[u];
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].to;
		if(v==rt) continue;
		dfs(v,rt);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
	return f[u][0];
}
int main(){
	scanf("%d",&n);
	for(int v=1,u;v<=n;v++){
		scanf("%d %d",&w[v],&u);
		adde(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			r1=r2=0;
			findd(i,i);
			if(r1){
				LL res1=dfs(r1,r1);
				LL res2=dfs(r2,r2);
				sum+=max(res1,res2);
			}
			
		}
	}
	printf("%lld\n",sum);
	return 0;
}

另一种写法：双向边

#include<queue>
#include<iostream>
#include<algorithm> 
typedef long long LL;
#define INF 1e9
using namespace std;
const int maxn=1e6+10;
int n,head[maxn],w[maxn],idx=1;
LL f[maxn][2],sum;
int r1,r2,vis[maxn];
struct node{
	int to,nex;
}e[maxn<<1];  //双向边 
int be[maxn<<1];//双向边 
void adde(int x,int y){  //单向边 
	e[++idx]={y,head[x]}; 
	head[x]=idx;
}
bool findd(int x,int inv){  //找出两个根 
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nex){
		if(i==(inv^1)) continue; //是反向边 
		int v=e[i].to;
		if(!vis[v]){
			if(findd(v,i)) return 1;
		} else{
			r1=x;r2=v;be[i]=1;be[i^1]=1; //标记正反向都不能走
			return 1; 
		}
	}
	return 0;
}

LL dfs(int u,int inv){ //树上dp 
	vis[u]=1;
	f[u][0]=0;f[u][1]=w[u];
	for(int i=head[u];i;i=e[i].nex){
		int v=e[i].to;
		if(be[i]||i==(inv^1)) continue;
		dfs(v,i);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
	return f[u][0];
}
int main(){
	scanf("%d",&n);
	for(int v=1,u;v<=n;v++){
		scanf("%d %d",&w[v],&u);
		adde(u,v);adde(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			r1=r2=0;
			findd(i,0);
			if(r1){
				LL res1=dfs(r1,0);
				LL res2=dfs(r2,0);
				sum+=max(res1,res2);
			}
			
		}
	}
	printf("%lld\n",sum);
	return 0;
}