Cod sursa(job #2616775)

Utilizator bigmixerVictor Purice bigmixer Data 19 mai 2020 22:43:44
Problema Diametrul unui arbore Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=100005;

// Diametrul in O(n) cu DFS

int n,timp=-1,height[nmax],max_a,max_ab,max_abc,ans;
vector<int>nod[nmax];

bitset<nmax>viz;

void mix(){
    int h=height[timp];
    int x=max_a,y=max_ab;
    if(timp>=0){
        max_a=max(max_a,h);
    }
    if(timp>=1){
        max_ab=max(max_ab,x-2*h);
    }
    if(timp>=2){
        max_abc=max(max_abc,y+h);
    }
}

void DFS(int s,int h){
    ++timp;
    viz[s]=1;
    height[timp]=h;
    mix();
    for(auto it:nod[s]){
        if(!viz[it]){
            DFS(it,h+1);
            timp++;
            height[timp]=h;
            mix();
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    cin >> n;
    for(int i=1;i<n;i++){
        int x,y;
        cin >> x >> y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }
    DFS(1,0);
    cout << max_abc+1 << '\n';
}