Cod sursa(job #586020)

Utilizator robigiirimias robert robigi Data 30 aprilie 2011 13:19:19
Problema Guvern Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.53 kb
#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;
}