Cod sursa(job #1584976)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 30 ianuarie 2016 17:24:27
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

const int Mn = 1e5 + 6;

int n,pos = 0;
int dp[Mn];
char buff[Mn];
vector< int > g[Mn];

void read(int &num)
{
    num = 0;
    char sign = '+';

    while (!isdigit(buff[pos]))
    {
        sign = buff[pos];

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    while (isdigit(buff[pos]))
    {
        num = num * 10 + buff[pos] - '0';

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    if (sign == '-')
       num *= -1;
}

bool comp(int a,int b)
{
    return (dp[a] > dp[b]);
}

int dfs(int node,int parent)
{
    if (g[node].size() == 0)
       return 0;

    for (int it = 0;it < g[node].size();it++)
        if (g[node][it] != parent)
           dp[g[node][it]] = dfs(g[node][it],node);

    sort(g[node].begin(),g[node].end(),comp);
    dp[node] = 0;
    bool b = 1;

    for (int it = 0;it < g[node].size();it++)
        if (dp[node] < dp[g[node][it]] + it + b && g[node][it] != parent)
           dp[node] = dp[g[node][it]] + it + b;
      else
        if (g[node][it] == parent)
           b = 0;

    return dp[node];
}

int main()
{
    freopen("zvon.in","r",stdin);
    freopen("zvon.out","w",stdout);

     int t;
     read(t);

     for (;t;t--)
     {
         read(n);

         for (int i = 1;i <= n;i++)
             g[i].clear();

         for (int i = 1;i < n;i++)
         {
             int x,y;
             read(x);
             read(y);
             g[x].push_back(y);
             g[y].push_back(x);
         }

         printf("%d\n",dfs(1,0));
     }

  return 0;
}