RT，点1WA，点3AC，其他TLE（好像死循环）

思路是对于每一棵基环树找环，然后对环上每个点的树做一遍树形dp，然后对着环做一次环形dp

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int inline read()
{
	int ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans*f;
}
const int N=1e6+5;
int p[N],c[N],v[N],head[N],fa[N],is[N];
ll f[N][2],g[N][2];
ll n,tot,cnt,start,sum,ans;
struct edge
{
	int to,nxt;
}e[N];
void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void check(int now)//找环
{
	v[now]=1;
	is[now]=1;
	if(v[fa[now]]) start=now;
	else check(fa[now]);
}
void dfs(int now,int fa)//树形dp
{
	v[now]=1;
	f[now][1]=p[now];
	for(int i=head[now];i;i=e[i].nxt)
	{
		if(e[i].to==fa||is[e[i].to]) continue;
		dfs(e[i].to,now);
		f[now][0]+=max(f[e[i].to][1],f[e[i].to][0]);
		f[now][1]+=f[e[i].to][0];
	}
}
void dp()//环形dp
{
	for(int i=1;i<=tot;i++) g[i][0]=g[i][1]=-2e9;
	g[1][0]=f[c[1]][0];
	for(int i=2;i<=tot;i++)
	{
		g[i][1]=g[i-1][0]+f[c[i]][1];
		g[i][0]=max(g[i-1][1],g[i-1][0])+f[c[i]][0];
	}
	ans=max(g[tot][0],g[tot][1]);
	for(int i=1;i<=tot;i++) g[i][0]=g[i][1]=-2e9;
	g[1][1]=f[c[1]][1];
	for(int i=2;i<=tot;i++)
	{
		g[i][1]=g[i-1][0]+f[c[i]][1];
		g[i][0]=max(g[i-1][1],g[i-1][0])+f[c[i]][0];
	}
	ans=max(ans,g[tot][0]);	
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		p[i]=read();
		fa[i]=read();
		add(fa[i],i);
	}
	for(int i=1;i<=n;i++)
	{
		if(v[i]) continue;
		check(i);
		tot=0;
		int x=start;
		do
		{
			c[++tot]=x;
			x=fa[x];
		}while(x!=start);
		for(int j=1;j<=tot;j++)
		dfs(c[j],0);
		dp();
		sum+=ans; 
	}
	cout<<sum;
	return 0;
}