제출 #1291216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291216		LIA	Hard route (IZhO17_road)	C++17	19 / 100	3 ms	1344 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) {
    unordered_map<ll, ll> f;
    for (auto &p : a)
      f[p.first] += p.second;

    v<ll> d;
    d.reserve(f.size());
    for (auto &kv : f)
      d.push_back(kv.first);
    sort(d.begin(), d.end(), greater<ll>());

    ll H = d[0], S = 0, T = 0, ways = 0;
    if (d.size() >= 3) {
      S = d[1];
      T = d[2];
      ways = (S != T) ? (f[S] * f[T]) : (f[S] * (f[S] - 1) / 2);
    } else if (d.size() == 2) {
      S = d[1];
      if (f[S] >= 2) {
        T = S;
        ways = f[S] * (f[S] - 1) / 2;
      }
    } else {
      if (f[d[0]] >= 3) {
        S = d[0];
        T = d[0];
        ways = f[d[0]] * (f[d[0]] - 1) / 2;
      }
    }

    if (ways > 0) {
      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 || 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