Cod sursa(job #3278725)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 20 februarie 2025 17:09:51
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 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];
int rasp;

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;
        
    rasp = -1;
    
}

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;
    
    //cout << nod << ' ' << timp << endl;
    
    rasp = max(rasp, timp);
    
    vector<pair<int, int>> aux;
    
    // for(int next : adj[nod])
    //     aux.push_back({dp[next], next});
        
    // sort(aux.begin(), aux.end(), greater<pair<int, int>>());
    
    // for(auto next : aux){
        
    //     if(!marked[next.second])
    //         rez(next.second, timp + 1);
        
    // }
    
    if(adj[nod].size() == 1){
        
        return;
        
    }
    
    
    sort(adj[nod].begin(), adj[nod].end(), cmp);
    
    int cnt = 0;
    for(int next : adj[nod])
        if(!marked[next]){
            
             cnt ++;
            rez(next, timp + cnt);
            
        }
    
}

void dfs(int nod){
    
    marked[nod] = true;
    
    if(adj[nod].size() == 1){
        
        dp[nod] = 1;
        return;
        
    }
        
    
    for(int next : adj[nod]){
        
        if(!marked[next]){
            
            dfs(next);
            
            dp[nod] += dp[next];
            
        }
        
    }
    
}

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
    
    dfs(1);
        
    for(int i=1; i<=n; i++)
        marked[i] = false;
        
    rez(1, 0);
    
    g << rasp << "\n";
    
}

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

    return 0;
}