-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGCPC11J.cpp
135 lines (125 loc) · 2.87 KB
/
GCPC11J.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 1e9
typedef long long ll;
typedef long double ld;
typedef unsigned long long int ul;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<float> vf;
typedef vector <ld> vd;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define vec(x) vector<x >
#define z size()
#define get1(x) cin>>x
#define get2(x, y) cin>>x>>y
#define get3(x, y, z) cin>>x>>y>>z
#define put(x) cout<<x
#define pls(x) cout<<x<<' '
#define pln(x) cout<<x<<"\n"
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=b-1;i>=a;i--)
#define vput(a) f(i,0,a.z) pls(a[i]); nl;
#define vget(v) f(i,0,v.z) get1(v[i]);
#define vsort(v) sort(v.begin(),v.end())
#define all(v) v.begin(),v.end()
#define vuni(v) v.erase(unique(all(v)),v.end())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define total(v) accumulate(all(v),ll(0))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define bs(v,x) binary_search(all(v),x)
#define lb(v,x) lower_bound(all(v),x)-v.begin()
#define ub(v,x) upper_bound(all(v),x)-v.begin()
#define parray(a,n) f(i,0,n) pls(a[i]); nl;
#define ppair(x) cout<<x.first<<' '<<x.second<<"\n";
#define vp(x,y) vector<pair<x,y> >
#define p(x,y) pair<x,y >
#define endl '\n'
#define nl cout<<'\n';
#define w(a) while(a--)
#define wh(a) while(a)
ll maxi=LLONG_MAX;
ll mini=LLONG_MIN;
void fast() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void tick(){
static clock_t oldt;
clock_t newt=clock();
double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;
oldt = newt;
cout << '\n' << "The execution time is : " << diff << '\n';
}
map <int, vector <int> > adjList;
void bfs(int src, bool visited[], int dist[]){
queue <int> q;
q.push(src);
visited[src] = true;
while(!q.empty()){
int node = q.front();
q.pop();
for(int neigh: adjList[node]){
if(!visited[neigh]){
q.push(neigh);
dist[neigh] = dist[node] + 1;
visited[neigh] = true;
}
}
}
// return ans;
}
int main(void)
{
fast();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
get1(t);
w(t){
adjList.clear();
int n;
get1(n);
f(i, 0, n-1){
int u, v;
get2(u, v);
adjList[u].pb(v);
adjList[v].pb(u);
}
int dist[n] = {0};
// int ans = INT_MAX;
bool visited[n] = {false};
bfs(0, visited, dist);
int tmp = 0, pos;
for(int i=0; i<n; i++){
if(tmp < dist[i]){
tmp = dist[i];
pos = i;
}
}
memset(dist, 0, sizeof(dist));
memset(visited, false, sizeof(visited));
bfs(pos, visited, dist);
int ans = 0;
for(int i=0; i<n; i++){
ans = max(ans, dist[i]);
}
if(ans&1){
ans=(ans+1)/2;
}
else
ans/=2;
pln(ans);
}
// tick();
}