제출 #899363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899363		MilosMilutinovic	Hard route (IZhO17_road)	C++14	0 / 100	1 ms	348 KiB

road

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  vector<int> mx(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    mx[v] = 1;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      mx[v] = max(mx[v], mx[u] + 1);
    }
  };
  long long res = 0;
  long long cnt = 1;
  for (int i = 0; i < n; i++) {
    Dfs(i, i);
    vector<int> f;
    for (int j : g[i]) {
      f.push_back(mx[j]);
    }
    sort(f.rbegin(), f.rend());
    if ((int) f.size() <= 2) {
      continue;
    }
    long long new_res = f[0] * (f[1] + f[2]);
    if (new_res < res) {
      continue;
    }
    vector<int> c(3);
    for (int x : f) {
      for (int k = 0; k < 3; k++) {
        if (f[k] == x) {
          c[k] += 1;
        }
      }
    }
    long long new_cnt = 0;
    if (f[0] == f[2]) {
      new_cnt = c[0] * 1LL * (c[0] - 1) * 1LL * (c[0] - 2) / 2;
    } else if (f[0] == f[1]) {
      new_cnt = c[0] * 1LL * (c[0] - 1) * 1LL * c[2];
    } else if (f[1] == f[2]) {
      new_cnt = c[0] * 1LL * c[1] * 1LL * (c[1] - 1) / 2;
    } else {
      new_cnt = c[0] * 1LL * c[1] * 1LL * c[2];
    }
    if (new_res == res) {
      cnt += new_cnt;
    } else {
      assert(new_res > res);
      res = new_res;
      cnt = new_cnt;
    }
  }
  cout << res << " " << cnt << '\n';
  return 0;
}

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