Pagini recente » Cod sursa (job #2307973) | Cod sursa (job #419150) | Cod sursa (job #1339072) | Cod sursa (job #2837075) | Cod sursa (job #586078)
Cod sursa(job #586078)
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
#include <vector>
#define NMAX 200005
#define pb push_back
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
vector <int> A[NMAX],C[NMAX];
set <pii> H;
int n,r,B[NMAX],D[NMAX],best[NMAX],poz,st,act[NMAX],F[NMAX],rez,dad[NMAX];
char viz[NMAX],marc[NMAX];
pii E[NMAX];
void read()
{
scanf("%d",&n);
int i,x,y;
for (i=1; i<n; i++)
{
scanf("%d%d",&x,&y);
A[x].pb(y);
A[y].pb(x);
}
for (i=1; i<=n; i++)
scanf("%d",&B[i]);
}
void dfs(int nod)
{
E[nod].f=++r;
viz[nod]=1;
int i,vec,act;
for (i=0; i<A[nod].size(); i++)
{
vec=A[nod][i];
if (!viz[vec])
{
dad[vec]=nod;
dfs(vec);
}
}
act=nod;
while (dad[act])
{
if (B[dad[act]]>B[nod])
{
if (!D[nod])
D[nod]=dad[act];
else
{
if (B[dad[act]]<B[D[nod]])
D[nod]=dad[act];
}
}
act=dad[act];
}
C[D[nod]].pb(nod);
E[nod].s=++r;
}
bool comp(int x,int y)
{
if (E[x].f<E[y].f)
return 1;
if (E[x].f>E[y].f)
return 0;
if (E[x].s>E[y].s)
return 1;
return 0;
}
inline int max(int x,int y)
{
return x>y ? x : y;
}
void dfs2(int nod)
{
viz[nod]=1; best[nod]=1;
int i,vec;
for (i=0; i<A[nod].size(); i++)
{
vec=A[nod][i];
if (!viz[vec])
dfs2(vec);
}
r=0;
for (i=0; i<C[nod].size(); i++)
{
vec=C[nod][i];
F[++r]=vec;
}
sort(F+1,F+r+1,comp);
for (i=1; i<=r; i++)
marc[i]=0;
for (i=1; i<=r; i++)
act[i]=best[F[i]];
for (i=1; i<=r; i++)
if (!marc[i])
{
st=i;
while (st+1<=r && E[F[st+1]].s<E[F[i]].s)
{
st++;
marc[st]=1;
act[i]=max(act[i],best[F[st]]);
}
}
for (i=1; i<=r; i++)
if (!marc[i])
best[nod]+=act[i];
}
int main()
{
freopen("guvern.in","r",stdin);
freopen("guvern.out","w",stdout);
read();
dfs(1);
memset(viz,0,sizeof(viz));
r=0;
dfs2(1);
int i;
for (i=1; i<=n; i++)
if (best[i]>rez && !D[i])
rez=best[i];
printf("%d\n",rez);
return 0;
}