T1 prime 质数序列 题意简述：给出n个数，要从中取若干数构成数列，使得两两相加为质数，要在数列长度最长的情况下元素和最大（保证唯一解），升序输出。 简单题，显然如果没有1的情况只能有两个数，有1两个及以上把所有1拿出来，看看能不能再放一个（当时以为1只能放2个，结果Bomb）。
T2 Bzoj2151 见：http://blog.csdn.net/mintgreentz/article/details/52204375
T3 etg 挺进 题意简述：一棵树断开任一条边，求剩余两部分最大直径之和。 简单树形dp（结果忘开int64）
const mxn=100001; type point=record v,x:int64; end; point2=record y,v,next:int64; end; var map:array[0..mxn*2] of point2; first,da,ua,u,lf:array[0..mxn] of int64;//downans upans up length_to_father dr:array[0..mxn,1..2] of point; //统计儿子答案最大的两个 d:array[0..mxn,1..3] of point;//down 统计向下最长三条边 g:array[0..3] of int64;//用于比较的几个数 n,i,x,y,v,s:longint; ans:int64; function max(a,b:int64):int64; begin if (a>b) then exit(a) else exit(b);end; procedure ins(x,y,v:longint); begin inc(s);map[s].y:=y;map[s].v:=v; map[s].next:=first[x];first[x]:=s; end; procedure dfs1(x,fa:longint); var t:longint; begin t:=first[x]; while t>0 do begin if map[t].y<>fa then begin dfs1(map[t].y,x); if d[map[t].y][1].v+map[t].v>=d[x][1].v then begin d[x][3]:=d[x][2]; d[x][2]:=d[x][1]; d[x][1].v:=d[map[t].y][1].v+map[t].v; d[x][1].x:=map[t].y; end else if d[map[t].y][1].v+map[t].v>=d[x][2].v then begin d[x][3]:=d[x][2]; d[x][2].v:=d[map[t].y][1].v+map[t].v; d[x][2].x:=map[t].y; end else if d[map[t].y][1].v+map[t].v>=d[x][3].v then begin d[x][3].v:=d[map[t].y][1].v+map[t].v; d[x][3].x:=map[t].y; end; if da[map[t].y]>=dr[x][1].v then begin dr[x][2]:=dr[x][1]; dr[x][1].v:=da[map[t].y]; dr[x][1].x:=map[t].y; end else if da[map[t].y]>=dr[x][2].v then begin dr[x][2].v:=da[map[t].y]; dr[x][2].x:=map[t].y; end; end else lf[x]:=map[t].v; t:=map[t].next; end; da[x]:=max(max(dr[x][1].v,dr[x][2].v),d[x][1].v+d[x][2].v); end; procedure dfs2(x,fa:longint); var i,j,t:longint; begin if (x=1) then begin u[x]:=0;ua[x]:=0;end else begin g[0]:=u[fa]; for i:=1 to 3 do g[i]:=d[fa][i].v*ord(d[fa][i].x<>x); for i:=0 to 2 do for j:=i+1 to 3 do if g[i]<g[j] then begin t:=g[i]; g[i]:=g[j]; g[j]:=t; end; u[x]:=g[0]+lf[x]; ua[x]:=max(ua[fa],g[0]+g[1]); if (dr[fa][1].x=x) then ua[x]:=max(ua[x],dr[fa][2].v) else ua[x]:=max(ua[x],dr[fa][1].v); end; t:=first[x]; while t>0 do begin if map[t].y<>fa then dfs2(map[t].y,x); t:=map[t].next; end; ans:=max(ans,da[x]+ua[x]); end; begin assign(input,'etg.in');reset(input); assign(output,'etg.out');rewrite(output); read(n); fillchar(first,sizeof(first),0);s:=0; for i:=1 to n-1 do begin read(x,y,v); ins(x,y,v); ins(y,x,v); end; fillchar(d,sizeof(d),0); fillchar(da,sizeof(da),0); fillchar(dr,sizeof(dr),0); dfs1(1,0); fillchar(u,sizeof(u),0); fillchar(ua,sizeof(ua),0); ans:=0; dfs2(1,0); writeln(ans); close(input);close(output); end.