Pagini recente » Cod sursa (job #2688083) | Cod sursa (job #3040174) | Cod sursa (job #523624) | Cod sursa (job #2703657) | Cod sursa (job #3278725)
#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;
}