Mai intai trebuie sa te autentifici.
Cod sursa(job #845271)
Utilizator | Data | 30 decembrie 2012 18:16:34 | |
---|---|---|---|
Problema | Asmax | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.36 kb |
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int sol,nod,x1,y1,i,n,nr,grad,cost[16009],s[16009],l[16009],t[16009],ap[16009],dp[16009];
vector < int > v[16009];
queue < int > cc;
void calc(int nod)
{
int i;
if(ap[nod]!=-1) return ;
if(v[nod].empty())
{
ap[nod]=1;
dp[nod]=cost[nod];
return ;
}
int s1=0;;
for(i=0;i<v[nod].size();i++)
{
calc(v[nod][i]);
if(dp[v[nod][i]]>0) s1=s1+dp[v[nod][i]];
}
ap[nod]=1;
dp[nod]=s1+cost[nod];
}
int main()
{
freopen("asmax.in","r",stdin);
freopen("asmax.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&cost[i]);
ap[i]=-1;
}
for(i=1;i<n;i++)
{
scanf("%d",&x1);
scanf("%d",&y1);
v[x1].push_back(y1);
s[x1]+=y1;
v[y1].push_back(x1);
s[y1]+=x1;
}
for(i=1;i<=n;i++)
{
l[i]=v[i].size();
if(l[i]==1) cc.push(i);
}
while(!cc.empty())
{
nod=cc.front();
cc.pop();
t[nod]=s[nod];
s[t[nod]]-=nod;
l[t[nod]]--;
if(l[t[nod]]==1) cc.push(t[nod]);
}
nod=1;
while(t[nod]!=0) nod=t[nod];
for(i=1;i<=n;i++)
v[i].clear();
for(i=1;i<=n;i++)
v[t[i]].push_back(i);
/////////////////////nod este acum tatal
calc(nod);
sol=-10000000;
for(i=1;i<=n;i++)
if(dp[i]>sol) sol=dp[i];
printf("%d\n",sol);
return 0;
}