其实已经准备退役了，但GDOI之前还是会继续学下去的！！当成兴趣在学，已经对竞赛失去信心了的样子，我还是回去跪跪文化课吧QAQ
第一道环套树DP...其实思想挺简单的，就把环拆开，分类处理。若拆成开的两个点是u,v，dp[i,0..1]分别表示第i位骑士不选和选
(1) 不选u，v点随意 (2)u随意，v点不选...
分类dp处理即可
1 const maxn=1000419; 2 type 3 edgetype=record 4 toward,next:longint; 5 end; 6 7 var 8 edge:array[0..maxn*2] of edgetype; 9 first:array[0..maxn] of longint; 10 val:array[0..maxn] of int64; 11 dp:array[0..maxn,0..1] of int64; 12 pd,vb,vc:array[0..maxn] of boolean; 13 root,vv,e,tot:longint; 14 n:longint; 15 function max(x,y:int64):int64; begin if x>y then exit(x) else exit(y); end; 16 17 procedure addedge(i,j:longint); 18 begin 19 edge[tot].toward:=j; 20 edge[tot].next:=first[i]; 21 first[i]:=tot; 22 inc(tot); 23 end; 24 25 procedure add(i,j:longint); 26 begin 27 addedge(i,j); addedge(j,i); 28 end; 29 30 procedure dfs(v,fa:longint); 31 var i,tmp:longint; 32 begin 33 pd[v]:=true; 34 i:=first[v]; 35 while i<>-1 do 36 begin 37 tmp:=edge[i].toward; 38 if not pd[tmp] then dfs(tmp,v) 39 else if tmp<>fa then 40 begin 41 vv:=v; 42 root:=tmp; 43 e:=i; 44 end; 45 i:=edge[i].next; 46 end; 47 end; 48 49 procedure dpb(v:longint); //ban u 50 var i,tmp:longint; 51 begin 52 dp[v,0]:=0; dp[v,1]:=val[v]; vb[v]:=true; 53 i:=first[v]; 54 while i<>-1 do 55 begin 56 tmp:=edge[i].toward; 57 if (i<>e) and (i xor 1<>e) and not vb[tmp] then 58 begin 59 dpb(tmp); 60 dp[v,0]:=dp[v,0]+max(dp[tmp,0],dp[tmp,1]); 61 dp[v,1]:=dp[v,1]+dp[tmp,0]; 62 end; 63 i:=edge[i].next; 64 end; 65 end; 66 67 procedure dpc(v:longint); //ban v; 68 var i,tmp:longint; 69 begin 70 dp[v,0]:=0; dp[v,1]:=val[v]; vc[v]:=true; 71 i:=first[v]; 72 while i<>-1 do 73 begin 74 tmp:=edge[i].toward; 75 if (i<>e) and (i xor 1 <>e) and not vc[tmp] then 76 begin 77 dpc(tmp); 78 dp[v,1]:=dp[v,1]+dp[tmp,0]; 79 if tmp=vv then dp[v,0]:=dp[v,0]+dp[tmp,0] 80 else dp[v,0]:=dp[v,0]+max(dp[tmp,0],dp[tmp,1]); 81 end; 82 i:=edge[i].next; 83 end; 84 end; 85 86 procedure solve; 87 var i:longint; 88 rec,ans:int64; 89 begin 90 ans:=0; 91 for i:= 1 to n do 92 if not pd[i] then 93 begin 94 rec:=0; root:=-1; dfs(i,-1); 95 dpb(root); rec:=dp[root,0]; 96 dpc(root); rec:=max(rec,max(dp[root,0],dp[root,1])); 97 inc(ans,rec); 98 end; 99 writeln(ans);100 end;101 102 procedure init;103 var i,x:longint;104 begin105 fillchar(first,sizeof(first),255);106 readln(n);107 tot:=0;108 for i:= 1 to n do109 begin110 readln(val[i],x);111 add(i,x);112 end;113 end;114 115 Begin116 init;117 solve;118 End.