Submission #1291211

#TimeUsernameProblemLanguageResultExecution timeMemory
1291211LIAHard route (IZhO17_road)C++17
0 / 100
0 ms332 KiB
//
// Created by liasa on 15/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
ll n;
v<v<ll>> g;
#define pll pair<ll, ll>
v<pll> dp, dpp;

pll merge(pll a, pll b) {
  if (b.first > a.first)
    return b;
  if (b.first < a.first)
    return a;
  return {a.first, a.second + b.second};
}

void dfs(ll node, ll par) {
  if (g[node].size() == 1 && par != -1) {
    dp[node] = {0, 1};
  }
  for (auto it : g[node]) {
    if (it != par) {
      dfs(it, node);
      pll cand = {dp[it].first + 1, dp[it].second};
      dp[node] = merge(dp[node], cand);
    }
  }
}

void dfs2(ll node, ll par) {
  v<ll> kids;
  for (auto it : g[node])
    if (it != par)
      kids.push_back(it);

  v<pll> suf(kids.size() + 1, {0, 0});
  for (ll i = (ll)kids.size() - 1; i >= 0; --i) {
    pll add = {dp[kids[i]].first + 2, dp[kids[i]].second};
    suf[i] = merge(add, suf[i + 1]);
  }

  pll left = {dpp[node].first + 1, dpp[node].second};

  lp(i, 0, (ll)kids.size()) {
    pll cur = merge(left, suf[i + 1]);
    dpp[kids[i]] = merge(dpp[kids[i]], cur);
    pll add = {dp[kids[i]].first + 2, dp[kids[i]].second};
    left = merge(left, add);
  }

  for (auto it : g[node])
    if (it != par)
      dfs2(it, node);
}

ll ans = 0, cnt = 0;

void dfs3(ll node, ll par) {
  v<pll> a;
  for (auto it : g[node])
    if (it != par)
      a.push_back({dp[it].first + 1, dp[it].second});

  if (par != -1)
    a.push_back(dpp[node]);

  if (a.size() >= 3) {
    sort(a.begin(), a.end(), [](const pll &x, const pll &y) {
      if (x.first != y.first)
        return x.first > y.first;
      return x.second > y.second;
    });
    ll H = a[0].first;
    ll S = a[1].first, T = a[2].first;

    ll cH = 0, cS = 0, cT = 0;
    for (auto &p : a) {
      if (p.first == H)
        cH += p.second;
      if (p.first == S)
        cS += p.second;
      if (p.first == T)
        cT += p.second;
      if (p.first < T)
        break;
    }

    ll ways = 0;
    if (S != T) {
      if (S == H)
        ways = (cS - 1) * cT;
      else
        ways = cS * cT;
    } else {
      if (S == H)
        ways = (cS - 1) * (cS - 2) / 2;
      else
        ways = cS * (cS - 1) / 2;
    }

    ll val = H * (S + T);
    if (val > ans) {
      ans = val;
      cnt = ways;
    } else if (val == ans) {
      cnt += ways;
    }

    for (auto it : g[node]) {
      if (it != par)
        dfs3(it, node);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  g.resize(n);
  lp(i, 0, n - 1) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  ll O = 0, T = 0;
  lp(i, 0, n) {
    if (g[i].size() == 1)
      O++;
    if (g[i].size() == 2)
      T++;
  }
  if (O == 2 && T == n - 2) {
    cout << 0 << " " << 1 << "\n";
    return 0;
  }

  dp.resize(n, {0, 0});
  dpp.resize(n, {0, 0});
  dpp[0].second = (g[0].size() == 1);
  dfs(0, -1);
  dfs2(0, -1);
  dfs3(0, -1);
  cout << ans << " " << cnt << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...