Submission #404613

#	Time	Username	Problem	Language	Result	Execution time	Memory
404613		rama_pang	Hard route (IZhO17_road)	C++17	100 / 100	844 ms	101652 KiB

road

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  // Let's fix a node u, and consider the 3 maximum distances
  // from u (where each is from different children). WLOG,
  // a <= b <= c. Then, the optimal hardness is c * (a + b).
  //
  // For (a, b, c) and node u, note that we can canonize the
  // route (a, b). For a fixed route (a, b), there might be
  // a lot of count(max(c)). However, if there is more than
  // 1 occurrence of length at least c, then at node u it
  // wouldn't be (a, b, c); instead it would be (a, c + x, c),
  // (we extend b to instead use the c-route since it's longer),
  // so it would be a different route. This way, c is unique
  // for a route (a, b) and only counted once.
  //
  // Now, we can use dynamic programming to count (a, b, c) in O(N).

  using lint = long long;
  array<lint, 2> ans = {0, 0};
  vector<array<lint, 2>> dn(N);
  vector<array<lint, 2>> up(N);

  const auto Add = [&](array<lint, 2> p, array<lint, 2> q) -> array<lint, 2> {
    if (p[1] == 0) return q;
    if (q[1] == 0) return p;
    if (p[0] != q[0]) return max(p, q);
    return {p[0], p[1] + q[1]};
  };

  const auto DfsDn = [&](const auto &self, int u, int p) -> void {
    dn[u] = {0, 1};
    for (auto v : adj[u]) if (v != p) {
      self(self, v, u);
      dn[u] = Add(dn[u], {dn[v][0] + 1, dn[v][1]});
    }
  };

  const auto DfsUp = [&](const auto &self, int u, int p) -> void {
    array<lint, 2> cur[2];
    cur[0] = up[u];
    cur[1] = {0, 0};
    for (auto v : adj[u]) if (v != p) {
      bool added = false;
      for (int i = 0; i < 2; i++) {
        if (cur[i][0] == dn[v][0] + 1) {
          cur[i][1] += dn[v][1];
          added = true;
          break;
        }
      }
      if (!added && dn[v][0] + 1 > cur[1][0]) {
        cur[1] = {dn[v][0] + 1, dn[v][1]};
        if (cur[1] > cur[0]) swap(cur[1], cur[0]);
      }
    }
    for (auto v : adj[u]) if (v != p) {
      if (dn[v][0] + 1 == cur[0][0] && dn[v][1] == cur[0][1]) {
        up[v] = {cur[1][0] + 1, cur[1][1]};
      } else if (dn[v][0] + 1 == cur[0][0]) {
        up[v] = {cur[0][0] + 1, cur[0][1] - dn[v][1]};
      } else {
        up[v] = {cur[0][0] + 1, cur[0][1]};
      }
      self(self, v, u);
    }
  };

  const auto DfsSolve = [&](const auto &self, int u, int p) -> void {
    array<lint, 4> cur[3];
    // (length, cnt, cnt if pick 2 different child, cnt if pick 3 different child)

    cur[0] = {up[u][0], up[u][1], 0, 0};
    cur[1] = {0, 0, 0, 0};
    cur[2] = {0, 0, 0, 0};

    for (auto v : adj[u]) if (v != p) {
      self(self, v, u);

      bool added = false;
      for (int i = 0; i < 3; i++) {
        if (cur[i][0] == dn[v][0] + 1) {
          cur[i][3] += dn[v][1] * cur[i][2];
          cur[i][2] += dn[v][1] * cur[i][1];
          cur[i][1] += dn[v][1];
          added = true;
          break;
        }
      }

      if (!added && dn[v][0] + 1 > cur[2][0]) {
        cur[2] = {dn[v][0] + 1, dn[v][1], 0, 0};
        if (cur[2] > cur[1]) swap(cur[2], cur[1]);
        if (cur[1] > cur[0]) swap(cur[1], cur[0]);
      }
    }

    if (cur[0][3] != 0) {         // Case a = b = c
      ans = Add(ans, {cur[0][0] * (cur[0][0] + cur[0][0]), cur[0][2]});
    } else if (cur[0][2] != 0) {  // Case a < b = c
      ans = Add(ans, {cur[0][0] * (cur[0][0] + cur[1][0]), cur[0][1] * cur[1][1]});
    } else if (cur[1][2] != 0) {  // Case a = b < c
      ans = Add(ans, {cur[0][0] * (cur[1][0] + cur[1][0]), cur[1][2]});
    } else {                      // Case a < b < c
      ans = Add(ans, {cur[0][0] * (cur[1][0] + cur[2][0]), cur[1][1] * cur[2][1]});
    }
  };

  int root = -1;
  for (int i = 0; i < N; i++) {
    if (adj[i].size() > 2) {
      root = i;
      break;
    }
  }

  if (root == -1) { // tree is line graph
    cout << 0 << ' ' << 1 << '\n';
    return 0;
  }

  DfsDn(DfsDn, root, -1);
  DfsUp(DfsUp, root, -1);
  DfsSolve(DfsSolve, root, -1);

  assert(ans[0] != 0 && ans[1] != 0);
  cout << ans[0] << ' ' << ans[1] << '\n';
  return 0;
}

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