Pagini recente » Cod sursa (job #3127909) | Cod sursa (job #1153999) | Cod sursa (job #3268359) | Cod sursa (job #1972701) | Cod sursa (job #3278762)
#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 last){
for(int next : adj[nod])
if(next != last){
rez(next, nod);
}
sort(adj[nod].begin(), adj[nod].end(), cmp);
int cnt = 0;
for(int next : adj[nod])
if(next != last){
cnt ++;
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);
//cout << endl << endl;
g << dp[1] << "\n";
}
int main()
{
int t;
f >> t;
for(int i=1; i<=t; i++)
solve();
return 0;
}