Pagini recente » Cod sursa (job #1570811) | Cod sursa (job #3148835) | Cod sursa (job #3156296) | Cod sursa (job #3272937) | Cod sursa (job #586020)
Cod sursa(job #586020)
#include <cstdio>
using namespace std;
FILE *f=fopen("guvern.in", "r");
FILE *g=fopen("guvern.out", "w");
typedef struct nod
{
int x;
struct nod *adr;
};
nod *l[200001];
nod *sus[200001];
nod *w[200001];
int n, v[200001];
int max=-1;
int nr;
inline int maxim(int x, int y)
{
if (x>y) return x;
return y;
}
void add(int x, int y)
{
if (l[x]==NULL)
{
l[x]=new nod;
l[x]->x=y;
l[x]->adr=NULL;
}
else
{
nod *p=new nod;
p->x=y;
p->adr=l[x];
l[x]=p;
}
}
void add2(int x, int y)
{
if (sus[x]==NULL)
{
sus[x]=new nod;
sus[x]->x=y;
sus[x]->adr=NULL;
}
else
{
nod *p=new nod;
p->x=y;
p->adr=sus[x];
sus[x]=p;
}
}
void add3(int x, int y)
{
if (w[x]==NULL)
{
w[x]=new nod;
w[x]->x=y;
w[x]->adr=NULL;
}
else
{
nod *p=new nod;
p->x=y;
p->adr=w[x];
w[x]=p;
}
}
int viz[200001];
void dfsus(int x, int min, int mini, int ini)
{
nod *p=sus[x];
while (p!=NULL)
{
if (v[p->x]<min && v[p->x]>v[ini])
{
min=v[p->x];
mini=p->x;
}
if (p->x==1 && mini!=0)
add3(mini, ini);
else dfsus(p->x, min, mini, ini);
p=p->adr;
}
}
void dfs(int x)
{
viz[x]=1;
nod *p=l[x];
while (p!=NULL)
{
if (viz[p->x]==0)
dfs(p->x);
else add2(x, p->x);
p=p->adr;
}
}
void dfs2(int x)
{
viz[x]=2;
nod *p=l[x];
while (p!=NULL)
{
if (viz[p->x]==1)
dfs2(p->x);
p=p->adr;
}
dfsus(x, 1000000001, 0, x);
}
void dfs3(int x)
{
++nr;
viz[x]=3;
nod *p=w[x];
while (p!=NULL)
{
if (viz[p->x]==2)
dfs3(p->x);
p=p->adr;
}
}
void read()
{
fscanf(f, "%d", &n);
for (int i=1; i<n; ++i)
{
int x, y;
fscanf(f, "%d%d", &x, &y);
add(x, y);
add(y, x);
}
for (int j=1; j<=n; ++j)
fscanf(f, "%d", &v[j]);
}
int main()
{
read();
dfs(1);
dfs2(1);
for (int j=1; j<=n; ++j)
{
if (viz[j]==2)
{
nr=0;
dfs3(j);
max=maxim(max, nr);
}
}
fprintf(g, "%d", max);
fclose(f);
fclose(g);
return 0;
}