Pagini recente » Cod sursa (job #2452670) | Cod sursa (job #1207368) | Cod sursa (job #1492242) | Cod sursa (job #2345636) | Cod sursa (job #2616772)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int nmax=100005;
// Diametrul in O(n) cu DFS
int n,timp=-1,height[nmax],max_a,max_ab,max_abc,ans;
vector<int>nod[nmax];
bitset<nmax>viz;
void mix(){
int h=height[timp];
int x=max_a,y=max_ab;
if(timp>=0){
max_a=max(max_a,h);
}
if(timp>=1){
max_ab=max(max_ab,x-2*h);
}
if(timp>=2){
max_abc=max(max_abc,y+h);
}
}
void DFS(int s,int h){
++timp;
viz[s]=1;
height[timp]=h;
mix();
for(auto it:nod[s]){
if(!viz[it]){
DFS(it,h+1);
timp++;
mix();
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
ifstream cin("darb.in");
ofstream cout("darb.out");
cin >> n;
for(int i=1;i<n;i++){
int x,y;
cin >> x >> y;
nod[x].push_back(y);
nod[y].push_back(x);
}
DFS(1,0);
cout << max_abc+1 << '\n';
}