Cod sursa(job #2403842)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 11 aprilie 2019 22:14:07
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("zvon.in");
ofstream g ("zvon.out");
const int nmax=1e5+3;
int usu[nmax],t,n,x,y,nod,viz[nmax],pwp,sol[nmax];
vector <int> v[nmax];
void dfs(int nod,int ant)
{
    usu[nod]=1;
    for(auto i:v[nod])
    {
        if(i==ant) continue;
        dfs(i,nod);
        usu[nod]+=usu[i];
    }
}
inline bool cmp(int &t1,int &t2)
{
    return usu[t1]>usu[t2];
}
queue <int> q;
void bfs()
{
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(auto i:v[nod])
        {
            if(viz[i]) continue;
            viz[i]=1;
            sol[i]=++sol[nod];
            pwp=max(pwp,sol[i]);
            q.push(i);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    f>>t;
    while(t--)
    {
        f>>n;
        for(int i=1;i<=n;++i) v[i].clear();
        for(int i=1;i<n;++i)
        {
            f>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        memset(usu,0,sizeof(usu));
        dfs(1,0);
        for(int i=1;i<=n;++i) sort(v[i].begin(),v[i].end(),cmp);
        pwp=0;
        memset(sol,0,sizeof(sol));
        memset(viz,0,sizeof(viz));
        bfs();
        g<<pwp<<'\n';
    }
    return 0;
}