Submission #1291214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291214		LIA	Hard route (IZhO17_road)	C++17	19 / 100	3 ms	1348 KiB

road

//
// 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;
const ll inf = 1e18;
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, {-inf, 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) {
      pll q = {dp[it].first + 1, dp[it].second};
      if (q.second > 0)
        a.push_back(q);
    }
  if (par != -1) {
    if (dpp[node].second > 0)
      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 cS = 0, cT = 0;
    for (auto &p : a) {
      if (p.first == S)
        cS += p.second;
      else if (p.first == T)
        cT += p.second;
      else if (p.first < T)
        break;
    }
    ll ways = (S != T) ? (cS * cT) : (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, {-inf, 0});
  dpp.resize(n, {-inf, 0});
  dpp[0] = {(g[0].size() == 1) ? 0 : -inf, (g[0].size() == 1) ? 1 : 0};
  dfs(0, -1);
  dfs2(0, -1);
  dfs3(0, -1);
  cout << ans << " " << cnt << "\n";
}

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