Cod sursa(job #3196211)

Utilizator Cazacu2006RazvanRazvan Cazacu Cazacu2006Razvan Data 23 ianuarie 2024 10:11:47
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("zvon.in");
ofstream fout("zvon.out");
int d[100001],maxim,n,t,r[100001],e[100001],minv[100001],maxv[100001];
vector <int> A[100001];
void dfs(int nod,int tata)
{
    for(auto i:A[nod])
    {
        dfs(i,nod);
    }
    if(A[nod].size()==0)
    {
        minv[nod]=1;
        maxv[nod]=1;
    }
    int elem=minv[nod]+A[tata].size();
    int maximv=max(elem,maxv[nod]+1);
    maxv[tata]=max(maxv[tata],maximv);
    minv[tata]=min(minv[tata],maximv);

}
void rez()
{
    fin>>n;
    for(int i=1;i<=n;i++){
        A[i].clear();
        d[i]=0;


        }
    maxim=0;

    d[1]=1;
    for(int i=1;i<n;i++)
    {
        int x,y;
        fin>>x>>y;
        A[x].push_back(y);
    }
    dfs(1,0);
    fout<<maxv[1]-1<<"\n";


}
int main()
{
    fin>>t;
    for(int i=1;i<=t;i++)
        rez();

    return 0;
}