Submission #404607

#	Time	Username	Problem	Language	Result	Execution time	Memory
404607		rama_pang	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	316 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 Item = pair<long long, long long>;
  Item ans = {0, 1};
  vector<Item> dn(N);
  vector<Item> up(N);

  const auto Add = [&](Item p, Item q) {
    if (p.first != q.first) return max(p, q);
    return Item(p.first, p.second + q.second);
  };

  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].first + 1, dn[v].second});
    }
  };

  const auto DfsUp = [&](const auto &self, int u, int p) -> void {
    Item cur[2];
    cur[0] = up[u];
    cur[1] = {0, 0};
    for (auto v : adj[u]) if (v != p) {
      Item tmp = Item(dn[v].first + 1, dn[v].second);
      if (tmp.first > cur[0].first) {
        cur[1] = cur[0];
        cur[0] = tmp;
      } else if (tmp.first == cur[0].first) {
        cur[0] = Add(cur[0], tmp);
      } else {
        cur[1] = Add(cur[1], tmp);
      }
    }
    for (auto v : adj[u]) if (v != p) {
      if (dn[v].first + 1 == cur[0].first && dn[v].second == cur[0].second) {
        up[v].first = cur[1].first + 1;
        up[v].second = cur[1].second;
      } else if (dn[v].first + 1 == cur[0].first) {
        up[v].first = cur[0].first + 1;
        up[v].second = cur[0].second - dn[v].second;
      } else {
        up[v].first = cur[0].first + 1;
        up[v].second = cur[0].second;
      }
      self(self, v, u);
    }
  };

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

    cur[0] = {up[u].first, up[u].second, 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].first + 1) {
          cur[i][3] += dn[v].second * cur[i][2];
          cur[i][2] += dn[v].second * cur[i][1];
          cur[i][1] += dn[v].second;
          added = true;
          break;
        }
      }

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

    if (cur[0][3] != 0) {         // Case a = b = c
      ans = Add(ans, Item(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, Item(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, Item(cur[0][0] * (cur[1][0] + cur[1][0]), cur[1][2]));
    } else {                      // Case a < b < c
      ans = Add(ans, Item(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;
    }
  }

  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);

  cout << ans.first << ' ' << ans.second << '\n';
  return 0;
}

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