Submit Info #21120

Problem Lang User Status Time Memory
Frequency Table of Tree Distance cpp (anonymous) AC 1183 ms 52.02 MiB

ケース詳細
Name Status Time Memory
almost_uni_00 AC 167 ms 25.90 MiB
almost_uni_01 AC 166 ms 25.90 MiB
example_00 AC 1 ms 0.67 MiB
line_00 AC 1183 ms 52.02 MiB
max_random_00 AC 348 ms 15.80 MiB
max_random_01 AC 355 ms 15.80 MiB
random_00 AC 203 ms 10.37 MiB
random_01 AC 248 ms 12.14 MiB
random_02 AC 80 ms 4.66 MiB
random_03 AC 293 ms 13.30 MiB
random_04 AC 20 ms 1.77 MiB
small_random_00 AC 2 ms 0.67 MiB
small_random_01 AC 1 ms 0.67 MiB
small_random_02 AC 1 ms 0.66 MiB
small_random_03 AC 1 ms 0.48 MiB
small_random_04 AC 1 ms 0.68 MiB
uni_00 AC 162 ms 26.64 MiB

#pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4") #include <bits/stdc++.h> using namespace std; constexpr int N = 1 << 19; using CD = complex <double>; const double PI = acosl(-1.0); int foo[N]; CD w[N], fftValues[N], result[N]; template <class P, class Q> inline void fft(CD *w, P *p, Q *y, int n, int k) { if (n > 1) { fft(w, p, y, n >>= 1, k << 1); fft(w, p + k, y + n, n, k << 1); for (int i = 0, j = 0; i < n; ++i, j += k) { CD r = w[j] * y[i + n]; y[i + n] = y[i] - r; y[i] += r; } } else { *y = *p; } }; int main() { // freopen("input.txt", "r", stdin); int n; scanf("%d", &n); vector < vector <int> > g(n); vector <long long> freq(n, 0LL); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } vector <int> sz(n), bs(n), kick(n, 0); function <void(int, int)> Size = [&](int v, int p) { sz[v] = 1; bs[v] = -1; for (auto to : g[v]) { if (to != p && !kick[to]) { Size(to, v); if (!~bs[v] || sz[to] > sz[bs[v]]) { bs[v] = to; } sz[v] += sz[to]; } } }; function <void(int, int, int, vector <int>&)> Height = [&](int v, int p, int dep, vector <int> &height) { while (height.size() <= dep) { height.push_back(0); } freq[dep] += 1; height[dep] += 1; for (auto to : g[v]) { if (to != p && !kick[to]) { Height(to, v, dep + 1, height); } } }; function <void(int)> Solve = [&](int v) { Size(v, -1); int half = sz[v] >> 1; while (~bs[v] && sz[bs[v]] >= half) { v = bs[v]; } vector < vector <int> > comps; int maxHeight = 0; for (auto to : g[v]) { if (!kick[to]) { comps.push_back(vector <int>()); Height(to, v, 1, comps.back()); if (maxHeight < comps.back().size()) { maxHeight = comps.back().size(); } } } vector <long long> cur(maxHeight << 1, 0LL); vector <int> store(maxHeight, 0); for (int i = 0; i < (int)comps.size(); ++i) { for (int ii = 0; ii < (int)comps[i].size(); ++ii) { store[ii] += comps[i][ii]; } } auto mul = [&](const vector <int> &values, int sign) { /* for (int i = 0; i < (int)values.size(); ++i) { for (int j = 0; j < (int)values.size(); ++j) { if (i + j < (int)cur.size()) { cur[i + j] += 1LL * sign * values[i] * values[j]; } } } return;*/ int n = (int)values.size(); int l = 1; while ((1 << l) < n) { ++l; } ++l; for (int i = 0; i < 1 << l; ++i) { w[i] = polar(1.0, 2.0 * PI * i / (1 << l)); foo[i] = (i < n ? values[i] : 0); } fft(w, foo, fftValues, 1 << l, 1); for (int i = 0; i < 1 << l; ++i) { fftValues[i] *= fftValues[i]; w[i] = conj(w[i]); } fft(w, fftValues, result, 1 << l, 1); for (int i = 0; i < (int)cur.size() && i < (1 << l); ++i) { long long what = (long long)(result[i].real() / (1 << l) + .5); cur[i] += sign * what; } }; mul(store, +1); /* for (int i = 0; i < maxHeight; ++i) { for (int j = 0; j < maxHeight; ++j) { cur[i + j] += 1LL * store[i] * store[j]; } }*/ for (int i = 0; i < (int)comps.size(); ++i) { /* for (int ii = 0; ii < (int)comps[i].size(); ++ii) { for (int jj = 0; jj < (int)comps[i].size(); ++jj) { cur[ii + jj] -= 1LL * comps[i][ii] * comps[i][jj]; } }*/ mul(comps[i], -1); } for (int i = 0; i < n && i < (maxHeight << 1); ++i) { freq[i] += cur[i] >> 1; } kick[v] = 1; for (auto to : g[v]) { if (!kick[to]) { Solve(to); } } }; Solve(0); for (int i = 1; i < n; ++i) { printf("%lld%c", freq[i], i == n - 1 ? '\n' : ' '); } return 0; }