Submission #1272184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272184		thewizardman	Hard route (IZhO17_road)	C++20	0 / 100	3 ms	576 KiB

road

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define N 500001

ll n;
pll dp[N], dp2[N], ans;
vector<int> adj[N];

inline pll operator+(const pll& l, const ll r) {
  return {l.first + r, l.second};
}

inline pll& operator+=(pll& l, const pll& r) {
  if (r.first > l.first) l = r;
  else if (r.first == l.first) l.second += r.second;
  return l;
}

ostream& operator<<(ostream& stream, const pll& p) {
  stream << p.first;
  stream << ' ';
  stream << p.second;
  return stream;
}

void dfs(int u, int p) {
  for (auto v: adj[u]) if (v != p) dfs(v, u);
  for (auto v: adj[u]) if (v != p) dp[u] += (dp[v] + 1);
}

void dfs2(int u, int p) {
  pll left = dp2[u] + 1;
  vector<pll> right;
  for (auto v: adj[u]) if (v != p) right.push_back(dp[v] + 2);
  for (int i = right.size() - 2; i >= 0; i--) right[i] += right[i+1];
  int i = 1;
  for (auto v: adj[u]) if (v != p) {
    pll cur = left;
    if (i < right.size()) cur += right[i];
    dp2[v] += cur;
    left += (dp[v] + 2);
    i++;
  }
  right.clear();
  for (auto v: adj[u]) if (v != p) dfs2(v, u);
}

void dfs3(int u, int p) {
  for (auto v: adj[u]) if (v != p) dfs3(v, u);
  vector<pll> a;
  a.push_back({0, 0});
  for (auto v: adj[u]) if (v != p) a.push_back(dp[v] + 1);
  if (u != 1) a.push_back(dp2[u]);
  a.push_back({0, 0});
  int n = a.size() - 2;
  // cout << u << '\n'; for (auto e: a) cout << e << ' '; cout << '\n';
  vector<vector<pll>> l, r;
  l.resize(n+2, vector<pll>(3));
  r.resize(n+2, vector<pll>(3));
  l[0][0] = r[n+1][0] = {0, 1};
  for (int i = 1; i <= n; i++) for (int j = 1; j < 3; j++) {
    l[i][j] = l[i-1][j];
    if (l[i-1][j-1].first + a[i].first > l[i][j].first) {
      l[i][j].first = l[i-1][j-1].first + a[i].first;
      l[i][j].second = l[i-1][j-1].second * a[i].second;
    } else if (l[i-1][j-1].first + a[i].first == l[i][j].first) {
      l[i][j].second += l[i-1][j-1].second * a[i].second;
    }
  }
  for (int i = n; i >= 1; i--) for (int j = 1; j < 3; j++) {
    r[i][j] = r[i+1][j];
    if (r[i+1][j-1].first + a[i].first > r[i][j].first) {
      r[i][j].first = r[i+1][j-1].first + a[i].first;
      r[i][j].second = r[i+1][j-1].second * a[i].second;
    } else if (r[i+1][j-1].first + a[i].first == r[i][j].first) {
      r[i][j].second += r[i+1][j-1].second * a[i].second;
    }
  }
  for (int i = 1; i <= n; i++) {
    ans += {a[i].first*l[i-1][2].first, l[i-1][2].second};
    ans += {a[i].first*(l[i-1][1].first+r[i+1][1].first), l[i-1][1].second*r[i+1][1].second};
    ans += {a[i].first*r[i+1][2].first, r[i+1][2].second};
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    static int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> temp(3, 0);
  for (int i = 1; i <= n; i++) temp[adj[i].size()]++;
  if (temp[1] == 2 && temp[2] == n-2) {cout << 0 << ' ' << 1 << '\n'; return 0;}
  dp2[1].second = (adj[1].size() == 1);
  for (int i = 2; i <= n; i++) if (adj[i].size() == 1) dp[i].second = 1;
  dfs(1, 0);
  dfs2(1, 0);
  dfs3(1, 0);
  cout << ans;
}

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