Cod sursa(job #1584249)

Utilizator ZenusTudor Costin Razvan Zenus Data 29 ianuarie 2016 20:39:01
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 200009;

int n , x , y , mx , k , i , a , b , dist;
int d[nmax];
vector < int > g[nmax];

void df(int x , int z)
{
    d[x] = d[z] + 1;

    for (int i = 0 ; i < g[x].size() ; ++i)
    {
        int y = g[x][i];

        if (y == z) continue;

        df(y , x);
    }
}

int main()
{
//#ifndef ONLINE_JUDGE
freopen("test.in" , "r" , stdin);
freopen("test.out" , "w" , stdout);
//#endif

cin >> n; //>> x >> y;

for (i = 2 ; i <= n ; ++i)
{
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
}

df(1 , 0);

for (i = 1 ; i <= n ; ++i)
if (d[i] > mx) mx = d[i] , k = i;

memset(d , 0 , sizeof(d));

df(k , 0);

for (i = 1 ; i <= n ; ++i)
dist = max(dist , d[i]);

cout << dist << '\n';
return 0;
dist--;

if (x <= y)
cout << 1LL * x * dist + 1LL * y * (n - 1 - dist) << '\n';
else
{
    if (dist == 2) cout << 1LL * x + 1LL * y * (n - 2) << '\n';
    else cout << 1LL * y * (n - 1) << '\n';
}

return 0;
}