#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
#define ll long long
const int N=1e6+1;
int n;
int h[N],nt[N*2],to[N*2];
int cnt;
void add(int x,int y)
{
nt[cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
cnt++;
}
int val[N],vis[N];
int EDGE;
namespace dp
{
ll f[N][2];
pair < int , int > st_ed;
void dp(int x,int fa)
{
f[x][1]=val[x];
f[x][0]=0;
for(int i=h[x]; ~i; i=nt[i])
{
int y=to[i];
if(y==fa||i==EDGE||i==(EDGE^1))
continue;
dp(y,x);
f[x][1]+=f[y][0];
f[x][0]+=max(f[y][0],f[y][1]);
}
return;
}
ll work(pair < int , int > x)
{
st_ed=x;
ll ans=0;
dp(st_ed.first,-1);
ans=max(ans,f[st_ed.first][0]);
dp(st_ed.second,-1);
ans=max(ans,f[st_ed.second][0]);
//cout<<ans<<endl;
return ans;
}
}
namespace tree
{
int v[N];
pair < int , int > st_ed;
void dfs(int x,int id)
{
vis[x]=1;
for(int i=h[x]; ~i; i=nt[i])
{
int y=to[i];
if(i==(id^1))continue;
if(vis[y])
{
st_ed=make_pair(x,y);
EDGE=i;
}
else{
dfs(y,i);
}
}
}
pair < int , int > work(int i)
{
st_ed=make_pair (-1,-1);
dfs(i,-1);
//cout<<st_ed.first<<" "<<st_ed.second<<endl;
//cout<<EDGE<<endl;
return st_ed;
}
}
ll ans=0;
signed main()
{
//freopen("text.in","r",stdin);
memset(h,-1,sizeof(h));
scanf("%d",&n);
for(int i=1,x; i<=n; i++)
{
scanf("%d%d",&val[i],&x);
add(x,i),add(i,x);
}
for(int i=1; i<=n; i++)
{
if(vis[i])continue;
ans+=dp::work(tree::work(i));
}
printf("%lld",ans);
}
标签:cnt,int,ed,st,P2607,ZJOI2008,ans,pair,骑士
From: https://www.cnblogs.com/dadidididi/p/16816619.html