Pagini recente » Cod sursa (job #3223238) | Cod sursa (job #2930075) | Cod sursa (job #607487) | Cod sursa (job #3246160) | Cod sursa (job #2709497)
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG
const int N = 1e5 + 7, INF = 1e9 + 7;
int dist[N], q[N], t[N];
vector < int > adia[N];
vector < int > edges;
bitset < N > locked;
int n;
pair < int, int > bfs(int nod, bool mod = 1) {
fill(dist, dist + n, INF);
dist[nod] = 0;
if (mod)
t[nod] = -1;
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 (locked[i])
continue;
int y = edges[i] ^ x;
if (dist[y] == INF) {
dist[y] = dist[x] + 1, q[++dr] = y;
if (mod)
t[y] = i;
}
}
}
return {last, D};
}
int calc_diam(int A, vector < int > &diam) {
// if (adia[A].size() > 1) {
// cout << "Esti bou\n";
// exit(0);
// }
diam.clear();
int B = bfs(A).first;
int l(0), cur(0);
for (int i = B; i != A; i = edges[t[i]] ^ i) {
locked[t[i]] = 1;
cur = max(cur, bfs(i, 0).second + l);
diam.push_back(cur);
l++;
}
diam.push_back(l);
for (int i = B; i != A; i = edges[t[i]] ^ i)
locked[t[i]] = 0;
return B;
}
int main()
{
ifstream fin("revolta.in");
ofstream fout("revolta.out");
int t;
fin >> t;
while (t--) {
int a, b;
fin >> n;
edges.clear();
for (int i = 0; i < n; ++i)
adia[i].clear();
for (int i = 1; i < n; ++i) {
fin >> a >> b;
adia[a].push_back(edges.size());
adia[b].push_back(edges.size());
edges.push_back(a ^ b);
}
int A = bfs(0).first;
vector < int > diam1, diam2;
calc_diam(calc_diam(A, diam1), diam2);
reverse(diam1.begin(), diam1.end());
#ifdef DEBUG
for (int i : diam1)
fout << i << ' ';
fout << '\n';
for (int i : diam2)
fout << i << ' ';
fout << '\n';
#endif // DEBUG
int ans(diam1.front());
for (int i = 1; i < diam1.size(); ++i)
ans = min(ans, max(max(diam2[i - 1], diam1[i]), (diam2[i - 1] + 1) / 2 + (diam1[i] + 1) / 2 + 1));
fout << ans << '\n';
}
return 0;
}