题目传送门
好难啊，我太菜了，连题解都看不懂啊……orz教主JN，把一道如此难题讲得如此精简，JN是最强的！（这是JN邪教的信条！）
翻开题解，都是一群大佬在刷什么基环外向树，吓得我抱起了抱着抱着抱着我的我的我的我。（这TMD什么玩意儿？！）
这道题给出的是一张n个节点、n条边的有向图。但只要稍微脑补一下，其实是无向图。
题目并没有说整张图是联通的，所以这是一片基环外向树森林。
对于普通的树，我们直接树形DP就行了；
对于基环外向树，我们要考虑删去环上的一条边，这样这棵基环外向树就变成了普通的树了，然后对于删去的边的两端节点分别做一次树形DP。
令f[i][0]表示不取第i号节点的最大价值，f[i][1]则反之。
因为这两个节点之间是有边的，也就是这两个节点不能同时出现在答案集合中，设这两个节点分别为u和v，所以我们取max(f[u][0],f[v][0])加入答案即可。
附上AC代码：
#include <cstdio> #include <cctype> #include <algorithm> #define N 1001000 using namespace std; struct side{ int to,nt; }s[N<<1]; int n,x,a[N],num=1,h[N],fx,fy,edge; long long f[N][2],ans,tmp; bool b[N]; inline char nc(){ static char ch[100010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(int &a){ static char c=nc();int f=1; for (;!isdigit(c);c=nc()) if (c=='-') f-1; for (a=0;isdigit(c);a=a*10+c-'0',c=nc()); a*=f;return; } inline void add(int x,int y){ s[++num]=(side){y,h[x]},h[x]=num; s[++num]=(side){x,h[y]},h[y]=num; } inline void so(int x,int e){ b[x]=1; for (int i=h[x]; i; i=s[i].nt) if ((i^1)!=e){ if (b[s[i].to]){ fx=x,fy=s[i].to,edge=i; continue; } so(s[i].to,i); } return; } inline void work(int x,int e,int ed){ f[x][1]=a[x],f[x][0]=0; for (int i=h[x]; i; i=s[i].nt) if ((i^1)!=e&&i!=ed&&(i^1)!=ed){ work(s[i].to,i,ed); f[x][0]+=max(f[s[i].to][0],f[s[i].to][1]); f[x][1]+=f[s[i].to][0]; } return; } int main(void){ read(n); for (int i=1; i<=n; ++i) read(a[i]),read(x),add(x,i); for (int i=1; i<=n; ++i) if (!b[i]){ so(i,0); work(fx,0,edge),tmp=f[fx][0]; work(fy,0,edge),tmp=max(tmp,f[fy][0]); ans+=tmp; } printf("%lld",ans); return 0; }