Pagini recente » Cod sursa (job #2969768) | Cod sursa (job #174829) | Cod sursa (job #1130940) | Cod sursa (job #2000828) | Cod sursa (job #1243076)
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
struct aur{
int node,val;
};
aur upDown[100010],downUp[100010];
int N,i,x,y,z,dad[100010],distTata[100010],sol;
vector<pair<int,int> > V[100010];
void DFS(int X)
{
upDown[X].node = X;
for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
{
int fiu = it->first;
int dist = it->second;
if(fiu == dad[X])continue;
dad[fiu] = X;
distTata[fiu] = dist;
DFS(fiu);
if(upDown[fiu].val + dist > upDown[X].val)
{
upDown[X].val = upDown[fiu].val + dist;
upDown[X].node = upDown[fiu].node;
}
}
}
void DFS2(int X)
{
downUp[X].node = X;
for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
{
int fiu = it->first;
int dist = it->second;
if(fiu == dad[X])
{
if(downUp[fiu].val + dist > downUp[X].val)
{
downUp[X].val = downUp[fiu].val + dist;
downUp[X].node = downUp[fiu].node;
}
if(upDown[fiu].node == upDown[X].node)
for(vector<pair<int,int> >::iterator jt = V[fiu].begin(); jt != V[fiu].end(); jt++)
{
if(jt->first == X || jt->first == dad[fiu])continue;
if(upDown[jt->first].val + distTata[jt->first] + dist > downUp[X].val)
{
downUp[X].val = upDown[jt->first].val + distTata[jt->first] + dist;
downUp[X].node = upDown[jt->first].node;
}
}
else
{
if(upDown[fiu].val + dist > downUp[X].val)
{
downUp[X].val = upDown[fiu].val + dist;
downUp[X].node = upDown[fiu].node;
}
}
continue;
}
}
for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
{
int fiu = it->first;
int dist = it->second;
if(fiu != dad[X])
DFS2(fiu);
}
}
int main()
{
freopen("darb.in","r",stdin);
freopen("darb.out","w",stdout);
scanf("%d",&N);
for(i=1;i < N; i++)
{
scanf("%d%d",&x,&y);
V[x].push_back(make_pair(y,1));
V[y].push_back(make_pair(x,1));
}
int root = 1;
DFS(root);
DFS2(root);
for(i=1;i<=N;i++)
{
sol = max(upDown[i].val,sol);
sol = max(downUp[i].val,sol);
}
printf("%d\n",sol+1);
return 0;
}