Pagini recente » Cod sursa (job #1951404) | Borderou de evaluare (job #1409439) | Borderou de evaluare (job #1593305) | Borderou de evaluare (job #2907402) | Cod sursa (job #1970610)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define FORR(i, x, y) for(int i = x; i >= y; --i)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define sz() size()
#define nMax 100005
using namespace std;
bool ap[nMax];
int dp[nMax], T[nMax];
queue <int> C;
vector <int> v[nMax];
int main()
{
ifstream fin("darb.in");
ofstream fout("darb.out");
int n, x, y, ans = 0;
fin >> n;
FOR(i, 1, n - 1){
fin >> x >> y;
T[y] = x;
v[x].pb(y);
ap[x] = 1;
}
FOR(i, 1, n)
if(!ap[i]) C.push(i), dp[i] = 1, ap[i] = 1;
else ap[i] = 0;
while(!C.empty()){
x = C.front();
y = T[x];
C.pop();
if(!ap[y]) C.push(y), ap[y] = 1;
dp[y] = max(dp[y], dp[x] + 1);
ap[x] = 0;
}
int mx1, mx2;
FOR(i, 1, n)
if(v[i].sz() > 0){
mx1 = mx2 = 0;
FOR(j, 0, v[i].sz() - 1){
x = v[i][j];
if(dp[x] >= mx1) mx2 = mx1, mx1 = dp[x];
else if(dp[x] > mx2) mx2 = dp[x];
}
ans = max(ans, mx1 + mx2);
}
fout << ans + 1;
return 0;
}