原題：
https://jzoj.net/senior/#contest/show/2043/0
題目描述：
GDOI商場推出優(yōu)惠活動(dòng)纤子，以超低價(jià)出售若干種商品核蘸。但是鳍怨，商場為避免過分虧本选酗，規(guī)定某些商品不能同時(shí)購買蒿柳，而且每種超低價(jià)商品只能買一件饶套。身為顧客的你想獲得最大的實(shí)惠，也就是爭取節(jié)省最多的錢垒探。經(jīng)過仔細(xì)研究凤跑，發(fā)現(xiàn)商場出售的超低價(jià)商品中，不存在以下情況：
n(n>=3)種商品C1,C2,…..,Cn,其中Ci,Ci+1是不能同時(shí)購買的(i=1,2…,n-1)并且C1, Cn也不能同時(shí)購買叛复。
編程計(jì)算可以節(jié)省的最大金額數(shù)仔引。
輸入：
第一行兩個(gè)整數(shù)K,M(1<=K<=1000).其中K表示超低價(jià)商品數(shù)。K種商品的編號(hào)依次為1,2,…,K褐奥。M表示不能同時(shí)購買的商品對(duì)數(shù).接下來K行咖耘，第i行有一個(gè)整數(shù)Xi表示購買編號(hào)為i的商品可以節(jié)省的金額(1<=Xi<=100).再接下來M行，每行兩個(gè)數(shù)A ,B,表示A和B不能同時(shí)購買撬码，1<=A<=K,1<=B<=K,A<>B
輸出：
僅一個(gè)整數(shù)儿倒，表示能節(jié)省的最大金額數(shù)。
樣例輸入：
3 1 1 1 1 1 2
樣例輸出：
2
分析：
經(jīng)典的樹形DP······
實(shí)現(xiàn)：
uses math;
var
p,t:array[1..1000,0..500]of longint;
c:array[1..1000]of longint;
v:array[1..1000]of boolean;
f:array[1..2,1..1000]of longint;
n,m,a,b,s,i:longint;
procedure make(x:longint);
var
i:longint;
begin
v[x]:=true;
for i:=1 to p[x,0] do
if not v[p[x,i]] then
begin
t[x,0]:=t[x,0]+1;
t[x,t[x,0]]:=p[x,i];
make(p[x,i]);
end;
end;
procedure dg(x:longint);
var
i:longint;
begin
if t[x,0]=0 then
begin
f[1,x]:=0;
f[2,x]:=c[x];
exit;
end;
for i:=1 to t[x,0] do dg(t[x,i]);
for i:=1 to t[x,0] do
begin
f[1,x]:=f[1,x]+max(f[1,t[x,i]],f[2,t[x,i]]);
f[2,x]:=f[2,x]+f[1,t[x,i]];
end;
f[2,x]:=f[2,x]+c[x];
end;
begin
readln(n,m);
for i:=1 to n do readln(c[i]);
for i:=1 to m do
begin
readln(a,b);
p[a,0]:=p[a,0]+1;p[a,p[a,0]]:=b;
p[b,0]:=p[b,0]+1;p[b,p[b,0]]:=a;
end;
for i:=1 to n do
if p[i,0]=0 then s:=s+c[i]
else
if not v[i] then
begin
make(i);
dg(i);
s:=s+max(f[1,i],f[2,i]);
end;
writeln(s);
end.
