Submit Info #21122

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

ケース詳細
Name Status Time Memory
almost_uni_00 AC 324 ms 16.41 MiB
almost_uni_01 AC 316 ms 16.49 MiB
example_00 AC 1 ms 0.74 MiB
line_00 AC 1316 ms 51.38 MiB
max_random_00 AC 521 ms 16.05 MiB
max_random_01 AC 521 ms 16.03 MiB
random_00 AC 311 ms 10.55 MiB
random_01 AC 383 ms 12.27 MiB
random_02 AC 124 ms 4.93 MiB
random_03 AC 426 ms 13.52 MiB
random_04 AC 35 ms 1.91 MiB
small_random_00 AC 2 ms 0.79 MiB
small_random_01 AC 1 ms 0.77 MiB
small_random_02 AC 1 ms 0.77 MiB
small_random_03 AC 2 ms 0.67 MiB
small_random_04 AC 2 ms 0.81 MiB
uni_00 AC 315 ms 16.54 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; /** Fast input-output */ template <class T = int> inline T readInt(); inline double readDouble(); inline int readUInt(); inline int readChar(); // first non-blank character inline void readWord( char *s ); inline bool readLine( char *s ); // do not save '\n' inline bool isEof(); inline int getChar(); inline int peekChar(); inline bool seekEof(); inline void skipBlanks(); template <class T> inline void writeInt( T x, char end = 0, int len = -1 ); inline void writeChar( int x ); inline void writeWord( const char *s ); inline void flush(); static struct buffer_flusher_t { ~buffer_flusher_t() { flush(); } } buffer_flusher; /** Read */ static const int buf_size = 1 << 16; static unsigned char buf[buf_size]; static int buf_len = 0, buf_pos = 0; inline bool isEof() { if (buf_pos == buf_len) { buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin); if (buf_pos == buf_len) return 1; } return 0; } inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; } inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; } inline bool seekEof() { int c; while ((c = peekChar()) != -1 && c <= 32) buf_pos++; return c == -1; } inline void skipBlanks() { while (!isEof() && buf[buf_pos] <= 32U) buf_pos++; } inline int readChar() { int c = getChar(); while (c != -1 && c <= 32) c = getChar(); return c; } inline int readUInt() { int c = readChar(), x = 0; while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return x; } template <class T> inline T readInt() { int s = 1, c = readChar(); T x = 0; if (c == '-') s = -1, c = getChar(); else if (c == '+') c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return s == 1 ? x : -x; } inline double readDouble() { int s = 1, c = readChar(); double x = 0; if (c == '-') s = -1, c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); if (c == '.') { c = getChar(); double coef = 1; while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar(); } return s == 1 ? x : -x; } inline void readWord( char *s ) { int c = readChar(); while (c > 32) *s++ = c, c = getChar(); *s = 0; } inline bool readLine( char *s ) { int c = getChar(); while (c != '\n' && c != -1) *s++ = c, c = getChar(); *s = 0; return c != -1; } /** Write */ static int write_buf_pos = 0; static char write_buf[buf_size]; inline void writeChar( int x ) { if (write_buf_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0; write_buf[write_buf_pos++] = x; } inline void flush() { if (write_buf_pos) { fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0; fflush(stdout); } } template <class T> inline void writeInt( T x, char end, int output_len ) { if (x < 0) writeChar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n < output_len) s[n++] = '0'; while (n--) writeChar(s[n]); if (end) writeChar(end); } inline void writeWord( const char *s ) { while (*s) writeChar(*s++); } 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 = readInt(); // scanf("%d", &n); vector < vector <int> > g(n); vector <long long> freq(n, 0LL); for (int i = 0; i < n - 1; ++i) { int u = readInt(); int v = readInt(); // 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 <long long> cur(1 << 10); auto mul = [&](const vector <int> &values, int sign) { 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 < (1 << l); ++i) { long long what = (long long)(result[i].real() / (1 << l) + .5); if (what != 0) { if (cur.size() <= i) { cur.resize(i + 1); } cur[i] += sign * what; } } }; int maxHeight = 0; vector <int> store(maxHeight, 0); for (auto to : g[v]) { if (!kick[to]) { vector <int> comp; Height(to, v, 1, comp); if (maxHeight < comp.size()) { maxHeight = comp.size(); } if (store.size() <= maxHeight) { store.resize(maxHeight + 1); } for (int i = 0; i < (int)comp.size(); ++i) { store[i] += comp[i]; } mul(comp, -1); } } mul(store, +1); for (int i = 0; i < n && i < cur.size(); ++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) { writeInt(freq[i], i == n - 1 ? '\n' : ' '); } return 0; }