原题:P2607 [ZJOI2008] 骑士
就差最后一个点了，卡了二十多次常了，最后一个点是死活过不去，现在还差0.03s，求优化

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0;
    char c=getchar();
    while(c<47)
    {
        c=getchar();
    }
    while(c>47)
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}//快读
void wit(long long x)
{
    if(x!=0)
    {
        wit(x/10);
        putchar(x%10+'0');
    }
    return ;
}
void write(long long x,bool edl)
{
    if(x<=0)
    {
        if(x==0)
        {
            putchar('0');
        }else{
            putchar('-');
            wit(x*(-1));
        }
    }else{
        wit(x);
    }
    if(edl)
    {
        putchar('\n');
    }else{
        putchar(' ');
    }
    return ;
}//18~48行为快速输出
const int N=1e6;
int n,w,p,sp1,sp2,val[N+5];//val存点权，
bool re1[N+5][2]={false},re[N+5]={false};//用于判重
vector<int>a[N+5],tree[N+5];//a存边，tree用于后续建树
long long ans=0,dp[N+5][2],ans1,ans2;
void del(int p,int las)
{
	re[p]=true;
	for(int i=0;i<a[p].size();i++)
	{
		if(!re[a[p][i]])
		{
			del(a[p][i],p);
		}else{
			if(a[p][i]!=las)
			{
				sp1=a[p][i];
				sp2=p;
			}
		}
	}
}//del函数用于找出某个连通块的随机一条基环树环部分的边
void planttree(int p,int id)
{
	re1[p][id]=true;
	tree[p].clear();
	for(int i=0;i<a[p].size();i++)
	{
		if(!re1[a[p][i]][id])
		{
			tree[p].push_back(a[p][i]);
			planttree(a[p][i],id);
		}
	}
}//建树
void f1(int p)
{
	long long a1=val[p],a2=0;
	for(int i=0;i<tree[p].size();i++)
	{
		f1(tree[p][i]);
		a1+=dp[tree[p][i]][0];
		a2+=max(dp[tree[p][i]][0],dp[tree[p][i]][1]);
	}
	dp[p][1]=a1;
	dp[p][0]=a2;
	return ;
}//dp，用递归实现向上转移
long long f(int p)
{
	long long h=0;
	for(int i=0;i<tree[p].size();i++)
	{
		f1(tree[p][i]);
		h+=max(dp[tree[p][i]][0],dp[tree[p][i]][1]);
	}
	return h;
}//假设根节点不取，对每个树求答案
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		w=read();
		p=read();
		a[i].push_back(p);
		a[p].push_back(i);
		val[i]=w;
	}//建图
	for(int i=1;i<=n;i++)
	{
		if(re[i])
		{
			continue;
		}
		del(i,-1);//割边，对某个连通块建树
		planttree(sp1,0);//对于割掉的那个边，取左端点为树的根节点建树
		ans1=f(sp1);//求左端点不取的时候该连通块的最大贡献
		planttree(sp2,1);
		ans2=f(sp2);//同理处理右端点
		ans+=max(ans1,ans2);
	}
	write(ans,true);//输出答案
    return 0;
}