骑士

这道题一看，似乎和是一样的，然而它并没有保证是一棵树

但是，对于每个连通块，必有相同的点数和边数，这样的图一定是一棵树上加一条边

这条边一定回使图中形成一个环，这种图貌似叫“基环树”。。

我们只要将不同的连通块分开处理，最后相加即可

对于一个基环树，只要找到环上的一条边，把它“拆掉”，分别从两个顶点dp一下就行了，

由于一条边的两个顶点不能同时选，就将f[u][0]与f[v][0]取一个max即可

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 1000100int n,value[MAXN],Head[MAXN],num=1,root1,root2,cut=-1;long long dp[MAXN][2],ans;bool vis[MAXN];struct NODE{    int to,next;} e[MAXN<<1];inline int read(){    int x=0; char c=getchar();    while(c<'0'||c>'9') c=getchar();    while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }    return x;}inline void add(int x,int y){    e[++num].to=y;    e[num].next=Head[x];    Head[x]=num;}void dfs(int t,int last){　　//找环    vis[t]=1;    for(int i=Head[t];i;i=e[i].next)     if(e[i].to!=last){        if(!vis[e[i].to]) dfs(e[i].to,t);        else { cut=i; root1=t; root2=e[i].to; }    }}void solve(int t,int last)　　//舞会{    dp[t][0]=0;    dp[t][1]=value[t];    for(int i=Head[t];i;i=e[i].next)     if(e[i].to!=last&&i!=cut&&i!=(cut^1))      {        int v=e[i].to;        solve(v,t);        dp[t][0]+=max(dp[v][1],dp[v][0]);        dp[t][1]+=dp[v][0];      }}int main(){    scanf("%d",&n);    int y;    for(int i=1;i<=n;i++){        scanf("%d%d",&value[i],&y);        add(i,y); add(y,i);     }    for(int i=1;i<=n;i++)     if(!vis[i]){        dfs(i,-1);        solve(root1,-1);        long long t=dp[root1][0];        solve(root2,-1);         ans+=max(t,dp[root2][0]);     }    printf("%lld\n",ans);    return 0;}