Introduction to base ring tree

Base ring tree ：

It's a kind of n A little bit n side , A graph in which only one ring exists is called a base ring tree （ Ring tree ）
There are three categories ：

• Undirected tree

• Out-Tree （ Each point has only one entry edge ）
  

• Introverted tree （ There is only one edge out of each point ）
  

The basic idea ：
1、 Deep search for ring
2、 Broken into trees , Carry out dp

example ： The knight

Ideas ：
1、 For each base ring tree, disconnect any edge on the ring , Make a tree for the two endpoints of this side respectively dp, Answer twice max
2、 Add up the of each base ring tree max

Code：

#include<bits/stdc++.h>
#define bug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
typedef long long ll;
int n,cnt,r1,r2;
int val[N],head[N];
bool vis[N];
struct Node {
    
	int to,nxt;
} e[N];
ll dp[N][2],res;
void add(int u,int v) {
    
	++cnt;
	e[cnt] = {
    v,head[u]};
	head[u] = cnt;
}
void Find(int u,int rt) {
    
	vis[u] = 1;
	for(int i=head[u]; i; i=e[i].nxt) {
    
		int v = e[i].to;
		if(v==rt) {
    
			r1=v;
			r2=u;
			return;
		}
		if(!vis[v]) Find(v,rt);
	}
}
ll dfs(int u,int rt) {
    
	dp[u][0] = 0;
	dp[u][1] = val[u];
	for(int i=head[u]; i; i=e[i].nxt) {
    
		int v = e[i].to;
		if(v==rt) continue;
		dfs(v,rt);
		dp[u][0] += max(dp[v][0],dp[v][1]);
		dp[u][1] += dp[v][0];
	}
	return dp[u][0];
}
int main() {
    

	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
    
		int w,u;
		scanf("%d%d",&val[i],&u);
		add(u,i);
	}
	for(int i=1; i<=n; i++) {
    
		if(!vis[i]) {
    
			r1=r2=0;
			Find(i,i);
			if(r1) {
    
				ll t1 = dfs(r1,r1);
				ll t2 = dfs(r2,r2);
				//cout<<t1<<" "<<t2<<endl;
				res += max(t1,t2);
			}
		}
	}
	printf("%lld",res);
	return 0;
}
/* 3 10 2 20 3 30 1 */

Writing is not good For reference only

---

Source of resources ： Dong Xiao algorithm