Pagini recente » Cod sursa (job #2780882) | Cod sursa (job #2424050) | Cod sursa (job #2625202) | Cod sursa (job #2705699) | Cod sursa (job #586251)
Cod sursa(job #586251)
#include <fstream>
# define inf 1000000005
using namespace std;
ifstream f ("guvern.in");
ofstream g ("guvern.out");
bool v[200005];
int d[200005],q[200005],w[200005],i,mm,xx,k,x,y,n;
struct nod
{
int info;
nod *urm;
}*a[200005],*p;
void df (int x)
{
nod *p;
v[x]=1;
k++;
q[x]=k;
p=a[x];
while (p)
{
if (v[p->info]==0)
df (p->info);
p=p->urm;
}
}
void maxx (int x)
{
nod *p;
p=a[x];
while (p)
{
if (q[x]<q[p->info])
{
if (d[xx]>=d[p->info])
if (mm<w[p->info])
mm=w[p->info];
maxx (p->info);
}
p=p->urm;
}
}
void dff (int x)
{
nod *p;
p=a[x];
while (p)
{
if (q[x]<q[p->info])
dff (p->info);
p=p->urm;
}
xx=x;
mm=-inf;
maxx (x);
if (mm!=-inf)
w[x]=mm+1;
else
w[x]=1;
}
int main()
{
f>>n;
for (i=1;i<n;i++)
{
f>>x>>y;
p=new nod;
p->info=y;
p->urm=a[x];
a[x]=p;
p=new nod;
p->info=x;
p->urm=a[y];
a[y]=p;
}
for (i=1;i<=n;i++)
f>>d[i];
df (1);
dff (1);
mm=-inf;
for (i=1;i<=n;i++)
if (mm<w[i])
mm=w[i];
g<<mm;
return 0;
}