제출 #93298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93298		toloraia	Hard route (IZhO17_road)	C++14	52 / 100	2056 ms	58516 KiB

road

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;

const int N = 5e5 + 5;

int n;
vector < int > g[N];
ll ans = -1, num;
ll D[N];

void dfs (int k, int p){
    D[k] = 0;
    for (int u: g[k]){
        if (u == p)
            continue;
        dfs (u, k);
        D[k] = max (D[k], D[u]);
    }
    D[k]++;
}

void go (int k, int p, ll d, ll dd){
    if ((int)g[k].size() == 1 && p != 0){
        if (ans == d * dd)
            num++;
        if (ans < d * dd){
            ans = d * dd;
            num = 1;
        }
    }
    ll x = 0, y = 0;
    for (int u: g[k]){
        if (u == p)
            continue;
        y = max (y, D[u]);
        if (x < y)
            swap (x, y);
    }
    for (int u: g[k]){
        if (u == p)
            continue;
        ll t = x;
        if (t == D[u])
            t = y;
        go (u, k, d + 1, max (dd, t));
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i = 1; i < n; i++){
        int u, v;
        cin>>u>>v;
        g[u].push_back (v);
        g[v].push_back (u);
    }
    for (int S = 1; S <= n; S++){
        if ((int)g[S].size() > 1)
            continue;
        dfs (S, 0);
        go (S, 0, 0, 0);
    }
    cout<<ans<<" "<<num / 2<<endl;
    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48