Cod sursa(job #1919574)

Utilizator UrsuDanUrsu Dan UrsuDan Data 9 martie 2017 20:05:43
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 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)
{
    if(depth[x]<=depth[y])
        return 1;
    else
        return 0;
}

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]);
        }
    }
}


int main()
{
    freopen("zvon.in","r",stdin);
    freopen("zvon.out","w",stdout);
    int t,n,i,x,y,j;
    scanf("%d",&t);
    for(j=1; j<=t; j++)
    {
        /* memset(viz,0,sizeof(viz));
        memset(depth,0,sizeof(depth));
        memset(timp,0,sizeof(timp));*/
        maxi=0;


        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;
            g[i].clear();
        }
    }
    return 0;
}