Pagini recente » Cod sursa (job #1182679) | Cod sursa (job #3193209) | Cod sursa (job #2884417) | Cod sursa (job #2101733) | Cod sursa (job #2709396)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, INF = 1e9 + 7;
int dist[N], q[N];
vector < int > adia[N];
int n;
pair < int, int > bfs(int nod) {
fill(dist, dist + n, INF);
dist[nod] = 0;
int st(0), dr(-1), D(0), last(nod);
q[++dr] = nod;
while (st <= dr) {
int x = q[st++];
D = dist[x];
last = x;
for (int i : adia[x])
if (dist[i] == INF)
dist[i] = dist[x] + 1, q[++dr] = i;
}
return {last, D};
}
int main()
{
ifstream fin("revolta.in");
ofstream fout("revolta.out");
int t;
fin >> t;
while (t--) {
int a, b;
fin >> n;
for (int i = 1; i < n; ++i) {
fin >> a >> b;
adia[a].push_back(b);
adia[b].push_back(a);
}
int e = bfs(0).first;
int d = bfs(e).second;
fout << (d > 2 ? d / 2 + 1 : d) << '\n';
}
return 0;
}