Cod sursa(job #3278753)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 20 februarie 2025 18:06:12
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("zvon.in");
ofstream g ("zvon.out");

const int NMAX = 1e5;

vector<int> adj[NMAX + 1];
bool marked[NMAX + 1];
int dp[NMAX + 1]; // dp[i] = cati subalterni are pula asta
vector<pair<int, int>> newadj[NMAX + 1];


void clear(){
    
    for(int i=1; i<=NMAX; i++)
        adj[i].clear();
        
    for(int i=1; i<=NMAX; i++)
        dp[i] = 0, marked[i] = false;
    
}

bool cmp(int a, int b){
    
    return dp[a] > dp[b] or (dp[a] == dp[b] and a < b);
    
}

void rez(int nod, int timp){
    
    marked[nod] = true;
    
    vector<pair<int, int>> aux;
    
    if(adj[nod].size() == 1){
        
        dp[nod] = 0;
        return;
        
    }
    
    sort(adj[nod].begin(), adj[nod].end(), cmp);
    
    int cnt = 0;
    for(int next : adj[nod])
        if(!marked[next]){
            
            cnt ++;
            rez(next, timp);
            
            dp[nod] = max(dp[nod], dp[next] + cnt);
            
        }
    
}

void solve(){
    
    clear();
    
    int n;
    f >> n;
    
    if(n == 1){
        
        // cout <<endl << 0 << endl << endl << "\n";
        g << 0 << "\n";
        return;
        
    }
    
    for(int i=1; i<n; i++){
        
        int x, y;
        f >> x >> y;
        
        adj[x].push_back(y);
        adj[y].push_back(x);
        
    }
    
    //acum construim "dp" - ul
        
    for(int i=1; i<=n; i++)
        marked[i] = false;
        
    rez(1, 0);
    
    g << dp[1] << "\n";
    
}

int main()
{
    int t;
    f >> t;
    
    for(int i=1; i<=t; i++)
        solve();

    return 0;
}