如题,应该是递归有问题?
#include <bits/stdc++.h>//MLE
using namespace std;
int n,d[1000005],num=1,head[1000005];
int u1,u2;
long long ans=0;
struct edge
{
int from,to;
int last;
}a[1000005];
void yadd(int from,int to)
{
a[num].from=from;
a[num].to=to;
a[num].last=head[from];
head[from]=num;
num++;
}
bool vis[1000005];
int o,o1;
void ydfs(int u)//找环上任意两点
{
vis[u]=1;
for(int t=head[u];t;t=a[t].last)
{
int y=a[t].to;
if(vis[y]==0)
ydfs(y);
else
o=t;
}
return ;
}
int tree[1000005][2],p1,p2;//0为不选,1为选
void ytreesearch(int u)//树型dp
{
tree[u][0]=0;
tree[u][1]=d[u];
for(int t=head[u];t;t=a[t].last)
{
int y=a[t].to;
if(t==o)
{
tree[y][1]=-999;
}
else
{
ytreesearch(y);
tree[u][0]+=max(tree[y][1],tree[y][0]);
tree[u][1]+=tree[y][0];
}
}
return ;
}
int main()
{
scanf("%d",&n);
for(int t=1;t<=n;t++)
{
scanf("%d%d",&d[t],&u2);
yadd(t,u2);
}
for(int t=1;t<=n;++t)
{
if(vis[t]) continue;
p1=0;p2=0;
ydfs(t);
o1=a[o].from;//o为删去的边
ytreesearch(o1);
p1=max(tree[o1][1],tree[o1][0]);
o1=a[o].to;
ytreesearch(o1);
p2=max(tree[o1][1],tree[o1][0]);
ans+=max(p1,p2);
}
printf("%d",ans);
return 0;
}