Cod sursa(job #586241)

Utilizator ProcopliucProcopliuc Adrian Procopliuc Data 30 aprilie 2011 14:13:38
Problema Guvern Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 1.48 kb
#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;

}