Cod sursa(job #1919359)

Utilizator UrsuDanUrsu Dan UrsuDan Data 9 martie 2017 19:02:54
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector< vector<int> >g(100010);

int depth[100010];
int timp[100010];
bool viz[100010];
int maxi;

bool cmp(int x,int y)
{
    return depth[x]<depth[y];
}

int maxim(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}

void dfs(int node)
{
    int i,l,maxi1;
    viz[node]=true;
    maxi1=0;
    l=g[node].size();
    for(i=0;i<l;i++)
    {
        if(viz[g[node][i]]==false)
        {
            dfs(g[node][i]);
            maxi1=maxim(maxi1,depth[g[node][i]]);
        }
    }
    depth[node]=maxi1+1;
}

void ans(int node)
{
    int i,l;
    viz[node]=true;
    maxi=maxim(maxi,timp[node]);
    l=g[node].size();
    for(i=l-1;i>=0;i--)
    {
        if(viz[g[node][i]]==false)
        {
            timp[g[node][i]]=timp[node]+l-i;
            ans(g[node][i]);
        }
        g[node].pop_back();
    }
}

void solve()
{
   /* memset(viz,0,sizeof(viz));
    memset(depth,0,sizeof(depth));
    memset(timp,0,sizeof(timp));*/
    maxi=0;

    int n,i,x,y;
    scanf("%d",&n);
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for(i=2;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end(),cmp);
        g[i].pop_back();
        viz[i]=false;
    }
    sort(g[1].begin(),g[1].end(),cmp);
    //memset(viz,0,sizeof(viz));
    ans(1);
    printf("%d\n",maxi);
    for(i=1;i<=n;i++)
    {
        depth[i]=0;
        timp[i]=0;
        viz[i]=false;
    }
}

int main()
{
    freopen("zvon.in","r",stdin);
    freopen("zvon.out","w",stdout);
    int t,i;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
        solve();
    return 0;
}