dfs找环
树上dp再套分类讨论
已经拍了一上午了
直接抑郁
#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
struct Node
{
int st;
bool ons;
int dfn;
long long val;
long long dp[2];
}node[1000011];
struct Edge
{
int des;
int next;
}edge[2000011];
int cnt=1;
int tail;
int sta[1000011];
long long gan[1000011][2];
inline void Add_edge(int u,int v)
{
cnt++;
edge[cnt].des=v;
edge[cnt].next=node[u].st;
node[u].st=cnt;
return;
}
void calc(int poi,int upon)
{
node[poi].dfn=1;
node[poi].dp[0]=0ll;
node[poi].dp[1]=node[poi].val;
for(int i=node[poi].st;i!=0;i=edge[i].next)
{
int flag=edge[i].des;
if(flag!=upon&&node[flag].ons==0)
{
calc(flag,poi);
node[poi].dp[0]+=max(node[flag].dp[0],node[flag].dp[1]);
node[poi].dp[1]+=node[flag].dp[0];
}
}
return;
}
inline void Pre(int le,int ri)
{
for(int i=le;i<=ri;i++)
{
gan[i][1]=node[sta[i]].dp[1];
gan[i][0]=node[sta[i]].dp[0];
}
return;
}
bool suc;
void dfs(int poi,int upon)
{
node[poi].dfn=1;
tail++;
sta[tail]=poi;
for(int i=node[poi].st;i!=0;i=edge[i].next)
{
if((i^1)==upon)continue;
int flag=edge[i].des;
if(node[flag].dfn==0)
{
dfs(flag,i);
}
else
{
suc=1;
int rnm=tail;
while(sta[rnm]!=flag)
{
node[sta[rnm]].ons=1;
rnm--;
}
node[sta[rnm]].ons=1;
rnm=tail;
while(sta[rnm]!=flag)
{
calc(sta[rnm],0);
rnm--;
}
calc(sta[rnm],0);
int fuck=tail-rnm+1;
if(fuck==2)
{
ans+=max(node[sta[rnm]].dp[0]+node[sta[tail]].dp[1],max(node[sta[rnm]].dp[1]+node[sta[tail]].dp[0],node[sta[rnm]].dp[0]+node[sta[tail]].dp[0]));
}
else if(fuck==3)
{
ans+=max(max(node[sta[tail]].dp[0]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[0],node[sta[tail]].dp[0]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[1]),max(node[sta[tail]].dp[0]+node[sta[rnm]].dp[1]+node[sta[rnm+1]].dp[0],node[sta[tail]].dp[1]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[0]));
}
else
{
int le=rnm+2,ri=tail-1;
Pre(rnm,tail);
for(int j=le+1;j<=ri;j++)
{
gan[j][1]=gan[j][1]+gan[j-1][0];
gan[j][0]=gan[j][0]+max(gan[j-1][1],gan[j-1][0]);
}
long long flag1=max(gan[ri][0],gan[ri][1])+gan[rnm][1];
le=rnm+1;
ri=tail;
Pre(rnm,tail);
for(int j=le+1;j<=ri;j++)
{
gan[j][1]=gan[j][1]+gan[j-1][0];
gan[j][0]=gan[j][0]+max(gan[j-1][1],gan[j-1][0]);
}
long long flag2=max(gan[ri][0],gan[ri][1])+gan[rnm][0];
ans+=max(flag1,flag2);
}
return;
}
if(suc==1)
{
return;
}
}
tail--;
return;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("mine.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int to;
scanf("%lld%d",&node[i].val,&to);
Add_edge(i,to);
Add_edge(to,i);
}
for(int i=1;i<=n;i++)
{
if(node[i].dfn==0)
{
tail=0;
suc=0;
dfs(i,0);
}
}
printf("%lld\n",ans);
return 0;
}
/*
3
10 2
20 3
30 1
*/
/*
13
20 3
15 3
36 4
23 5
17 6
32 7
19 8
21 4
30 6
11 7
10 12
20 13
30 11
*/