emm 上面那个代码有点问题，删边写错了（虽然好像因为数据很水没WA）
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> a[1000001],idx[1000001];
int n,m,u,v,i,j;
long long w[1000001],dp[1000001][2],dp2[1000001][2],ans;
bool book[1000001],book2[1000001],vis[1000001],del[1000001];
inline int read(){
int s=0;
char ch=getchar();
while(ch<='0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
void dpdfs(int x){
book[x]=true;
dp[x][1]=w[x];
int ll=a[x].size();
for(register int i=0;i<ll;i++){
int y=a[x][i];
if(del[idx[x][i]]||book[y])
continue;
dpdfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
}
void dpdfs2(int x){
book2[x]=true;
dp2[x][1]=w[x];
int ll=a[x].size();
for(register int i=0;i<ll;i++){
int y=a[x][i];
if(del[idx[x][i]]||book2[y])
continue;
dpdfs2(y);
dp2[x][1]+=dp2[y][0];
dp2[x][0]+=max(dp2[y][0],dp2[y][1]);
}
}
void dfs(int x,int pre){
vis[x]=true;
int ll=a[x].size();
for(register int i=0;i<ll;i++){
int y=a[x][i];
if(y==pre||del[idx[x][i]])
continue;
if(vis[y]){
u=x;v=y;
del[idx[x][i]]=true;
continue;
}
dfs(y,x);
}
}
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++){
w[i]=read();
u=read();
a[i].push_back(u);
a[u].push_back(i);
idx[i].push_back(i);
idx[u].push_back(i);
}
for(register int i=1;i<=n;i++){
if(vis[i])
continue;
u=v=0;
dfs(i,0);
dpdfs(u);
dpdfs2(v);
ans+=max(dp[u][0],dp2[v][0]);
}
printf("%lld",ans);
return 0;
}
```
by Cobalt @ 2018-08-11 20:00:28
换成链式前向星就AC了
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
int next;
int to;
};
edge a[2000100];
int n,m,u,v,i,j,head[1000100];
long long w[1000100],dp[1000100][2],dp2[1000100][2],ans,cnt;
bool book[1000100],book2[1000100],vis[1000100];
inline void add(int u,int v){
a[cnt]=(edge){head[u],v};
head[u]=cnt;
cnt++;
}
inline int read(){
int s=0;
char ch=getchar();
while(ch<='0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
void dpdfs(int x){
book[x]=true;
dp[x][1]=w[x];
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==-1||book[y])
continue;
dpdfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
}
void dpdfs2(int x){
book2[x]=true;
dp2[x][1]=w[x];
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==-1||book2[y])
continue;
dpdfs2(y);
dp2[x][1]+=dp2[y][0];
dp2[x][0]+=max(dp2[y][0],dp2[y][1]);
}
}
void dfs(int x,int pre){
vis[x]=true;
for(register int i=head[x];i+1;i=a[i].next){
int y=a[i].to;
if(y==pre||y==-1)
continue;
if(vis[y]){
u=x;v=y;
//cout<<a[i].to<<" "<<a[i^1].to<<endl;
a[i].to=-1;
a[i^1].to=-1;
continue;
}
dfs(y,x);
}
}
int main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++)
head[i]=-1;
for(register int i=1;i<=n;i++){
w[i]=read();
u=read();
add(u,i);
add(i,u);
}
for(register int i=1;i<=n;i++){
if(vis[i])
continue;
u=v=0;
dfs(i,0);
dpdfs(u);
dpdfs2(v);
ans+=max(dp[u][0],dp2[v][0]);
}
printf("%lld",ans);
return 0;
}
```
by Cobalt @ 2018-08-11 20:01:01
vector开了O2不是比前向星更快吗
by YZhe @ 2019-02-08 13:21:36