Submission #1291217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291217		LIA	Hard route (IZhO17_road)	C++17	100 / 100	546 ms	107648 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 && 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 val = 0;
    ll ways = 0;
    if (a[1].first != a[2].first) {
      ll n1 = 0, n2 = 0;
      for (auto &p : a) {
        if (p.first == a[1].first)
          n1 += p.second;
        else if (p.first == a[2].first)
          n2 += p.second;
        else if (p.first < a[2].first)
          break;
      }
      val = a[0].first * (a[1].first + a[2].first);
      ways = n1 * n2;
    } else {
      ll n1 = 0, n2 = 0;
      for (auto &p : a) {
        if (p.first == a[1].first) {
          n2 += n1 * p.second;
          n1 += p.second;
        } else if (p.first < a[1].first)
          break;
      }
      val = a[0].first * a[1].first * 2;
      ways = n2;
    }

    if (ways > 0) {
      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 || 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: 33 / 33
• Subtask 3: 48 / 48