记录编号	39102	评测结果	AAAAAAAAAAA
题目名称	子集	最终得分	100
用户昵称	SnowDancer	是否通过	通过
代码语言	Pascal	运行时间	0.023 s
提交时间	2012-07-04 17:21:23	内存使用	23.36 MiB

const
  maxN=10000;  maxE=2000000;
var
  dfn,low,stack,num:array[1..maxN] of longint;
  h,x,next:array[1..maxE] of longint;
  f,g:array[1..maxn,0..1] of longint;
  n,i,j,k,l,tot,top,index,m,t,temp0,temp1,ans:longint;
function max(x,y:longint):longint;
  begin if x>y then exit(x) else exit(y); end;
procedure DP;
  var
    i:longint;
  begin
    // chose First
    g[2,0]:=f[num[1],1]+f[num[2],0]; g[2,1]:=-maxlongint;
    for i:=3 to tot do begin
      g[i,0]:=max(g[i-1,0],g[i-1,1])+f[num[i],0];
      g[i,1]:=g[i-1,0]+f[num[i],1];
    end;
    temp0:=g[tot,0];
    // not chose First
    g[2,0]:=f[num[1],0]+f[num[2],0]; g[2,1]:=f[num[1],0]+f[num[2],1];
    for i:=3 to tot do begin
      g[i,0]:=max(g[i-1,0],g[i-1,1])+f[num[i],0];
      g[i,1]:=g[i-1,0]+f[num[i],1];
    end;
    f[num[tot],0]:=max(g[tot,0],temp0);
    f[num[tot],1]:=g[tot,1];
  end;
procedure calCutPoint(v:longint);
  var
    p,u:longint;
  begin
    p:=h[v];  inc(index);
    dfn[v]:=index; low[v]:=index;
    inc(top); stack[top]:=v;
    while p<>0 do begin
      u:=x[p];
      if dfn[u]=0 then begin
        calCutPoint(u);
        if low[u]<low[v] then low[v]:=low[u];
        if dfn[v]<=low[u] then begin
          tot:=0;
          repeat
            k:=stack[top]; dec(top);
            inc(tot); num[tot]:=k;
          until u=k;
          inc(tot); num[tot]:=v;
          DP;
        end;
      end else
        if low[v]>dfn[u] then low[v]:=dfn[u];
      p:=next[p];
    end;
  end;
begin
assign(input,'subseta.in'); reset(input);
assign(output,'subseta.out'); rewrite(output);
  readln(n);
  for i:=1 to n do read(f[i,1]);
  readln(m);
  for k:=1 to m do begin
    readln(i,j);
    inc(t);  x[t]:=j;
    next[t]:=h[i];  h[i]:=t;
    inc(t);  x[t]:=i;
    next[t]:=h[j];  h[j]:=t;
  end;
  for i:=n downto 1 do
    if dfn[i]=0 then begin
      calCutPoint(i);
      inc(ans,max(f[i,0],f[i,1]));
    end;
  writeln(ans);
close(input); close(output);
end.