Cod sursa(job #3273719)

Utilizator andrei.nNemtisor Andrei andrei.n Data 3 februarie 2025 17:03:18
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#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;
}