Pagini recente » Cod sursa (job #1981619) | Borderou de evaluare (job #567029) | Cod sursa (job #2546441) | Cod sursa (job #621921) | Cod sursa (job #3273719)
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int node,depth;
};
vector<int> v[100005];
Node nodes[100005];
int dp[100005], depth[100005];
void dfs(int node)
{
for(auto &son : v[node])
if(nodes[son].depth == -1)
{
nodes[son].depth = nodes[node].depth + 1;
dfs(son);
}
}
signed main()
{
ifstream fin ("darb.in");
ofstream fout ("darb.out");
ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
int n,a,b; fin>>n;
nodes[n].node = n;
nodes[n].depth = -1;
for(int i=1; i<n; ++i)
{
fin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
nodes[i].node = i;
nodes[i].depth = -1;
}
nodes[1].depth = 0;
dfs(1);
for(int i=1; i<=n; ++i)
v[i].erase(remove_if(v[i].begin(), v[i].end(), [&i](const int &x){return nodes[i].depth > nodes[x].depth;}), v[i].end());
sort(nodes+1, nodes+n+1, [](const Node &a, const Node &b){return a.depth > b.depth;});
for(int idx = 1; idx <= n; ++idx)
{
int node = nodes[idx].node, cnt = v[node].size();
if(cnt == 0)
{
dp[node] = depth[node] = 1;
continue;
}
int max1=0,max2=0;
for(auto &son : v[node])
{
dp[node] = max(dp[node], dp[son]);
if(depth[son] + 1 > max1)
{
max2 = max1;
max1 = depth[son] + 1;
}
else if(depth[son] + 1 > max2)
max2 = depth[son] + 1;
}
depth[node] = max1;
dp[node] = max(dp[node], max1 + max2 - 1);
}
fout<<dp[1];
return 0;
}