verify/yosupo/yosupo-frequency_table_of_tree_distance.test.cpp

• View this file on GitHub
• Last update: 2022-08-21 11:26:50-04:00
• Problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance

Depends on

• library/contest/template-full.hpp
• library/contest/template-minimal.hpp
• Sparse Table (library/data-structures/1d-range-queries/sparse-table.hpp)
• library/graphs/centroid-decomposition.hpp
• LCA RMQ (library/graphs/lca-rmq.hpp)
• library/misc/easy-io.hpp
• library/modular-arithmetic/mod-int.hpp
• library/modular-arithmetic/mod-int2.hpp
• library/polynomial/fast-fourier-transform.hpp
• library/polynomial/polynomial2.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"

#include "../../library/contest/template-full.hpp"
#include "../../library/graphs/centroid-decomposition.hpp"
#include "../../library/graphs/lca-rmq.hpp"
#include "../../library/polynomial/fast-fourier-transform.hpp"
#include "../../library/polynomial/polynomial2.hpp"

int main() {
	using namespace FFT;
	using namespace Polynomial;
	set_io("");
	int n;
	re(n);
	CentroidDecomposition cd;
	cd.init(n);
	LCARMQ lca;
	lca.init(n);
	vector<vi> g(n);
	f0r(i, n - 1) {
		int u, v;
		re(u, v);
		g[u].pb(v);
		g[v].pb(u);
		lca.ae(u, v);
		cd.ae(u, v);
	}
	lca.gen();
	cd.build();
	vl ans(n);
	function<vi(int)> dfs = [&](int u) { // return how many at dist x

		vi verts;
		vector<vl> polys;
		polys.pb({1});
		vl tmp;
		each(v, cd.cg[u]) {	
			auto res = dfs(v);
			each(x, res) verts.pb(x);
			tmp.assign(res.size() + 1, 0);
			each(x, res) {
				++tmp[lca.dist(x, u)];
			}
			while (tmp.back() == 0) tmp.pop_back();
			polys.pb(tmp);
		}	
		vl sum;
		each(x, polys) sum += x;
		vl res = sum * sum;
		each(x, polys) res -= x * x;
		res /= 2;
		f0r(i, sz(res)) {
			ans[i] += res[i];
		}
		verts.pb(u);
		return verts;
	};
	dfs(cd.root);
	f1r(i, 1, n) {
		pr(ans[i], ' ');
	}
	ps();
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"



#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<db, db> pd;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define resz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define r1f(i, a, b) for (int i = (b); i --> (a); )
#define r0f(i, a) r1f(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define each(a, x) for (auto& a : x)

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<V<V<T>>>;
template <class T> using VVVV = V<V<V<V<T>>>>;

template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& p) { 
  return os << "(" << p.first << ", " << p.second << ")"; 
}
template <typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream& os, const C& c) { 
  bool f = true; 
  os << "{"; 
  for (const auto& x : c) { 
    if (!f) 
      os << ", "; 
    f = false; os << x; 
  } 
  return os << "}"; 
}
template <typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template <typename T, typename... Args> void debug(string s, T x, Args... args) { 
  cerr << s.substr(0, s.find(',')) << " = " << x << " | "; 
  debug(s.substr(s.find(',') + 2), args...); 
}

constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))


inline namespace Helpers {
	//////////// is_iterable

	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable

	// this gets used only when we can call begin() and end() on that type

	template <class T, class = void> struct is_iterable : false_type {};
	template <class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
									  decltype(end(declval<T>()))
									 >
						   > : true_type {};
	template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;

	//////////// is_readable

	template <class T, class = void> struct is_readable : false_type {};
	template <class T> struct is_readable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cin >> declval<T&>()), istream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_readable_v = is_readable<T>::value;

	//////////// is_printable

	// // https://nafe.es/posts/2020-02-29-is-printable/

	template <class T, class = void> struct is_printable : false_type {};
	template <class T> struct is_printable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cout << declval<T>()), ostream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input {
	template <class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
	template <class T, class... U> void re(T& t, U&... u);
	template <class T, class U> void re(pair<T, U>& p); // pairs


	// re: read

	template <class T> typename enable_if<is_readable_v<T>, void>::type re(T& x) { cin >> x; } // default

	template <class T> void re(complex<T>& c) { T a, b; re(a, b); c = {a, b}; } // complex

	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i); // ex. vectors, arrays

	template <class T, class U> void re(pair<T, U>& p) { re(p.first, p.second); }
	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i) {
		for (auto& x : i) re(x); }
	template <class T, class... U> void re(T& t, U&... u) { re(t); re(u...); } // read multiple


	// rv: resize and read vectors

	void rv(std::size_t) {}
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u);
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u);
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u) {
		t.resize(N); re(t);
		rv(N, u...); }
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u) {
		rv(N2, u...); }

	// dumb shortcuts to read in ints

	void decrement() {} // subtract one from each

	template <class T, class... U> void decrement(T& t, U&... u) { --t; decrement(u...); }
	#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
	#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}
  
inline namespace ToString {
	template <class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

	// ts: string representation to print

	template <class T> typename enable_if<is_printable_v<T>, string>::type ts(T v) {
		stringstream ss; ss << fixed << setprecision(15) << v;
		return ss.str(); } // default

	template <class T> string bit_vec(T t) { // bit vector to string

		string res = "{"; for (int i = 0; i < (int)t.size(); ++i) res += ts(t[i]);
		res += "}"; return res; }
	string ts(vector<bool> v) { return bit_vec(v); }
	template <std::size_t SZ> string ts(bitset<SZ> b) { return bit_vec(b); } // bit vector

	template <class T, class U> string ts(pair<T, U> p); // pairs

	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v); // vectors, arrays

	template <class T, class U> string ts(pair<T, U> p) { return "(" + ts(p.first) + ", " + ts(p.second) + ")"; }
	template <class T> typename enable_if<is_iterable_v<T>, string>::type ts_sep(T v, string sep) { 
		// convert container to string w/ separator sep

		bool fst = 1; string res = "";
		for (const auto& x : v) { 
			if (!fst) res += sep;
			fst = 0; res += ts(x);
		}
		return res;
	}
	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v) {
		return "{" + ts_sep(v, ", ") + "}"; } 

	// for nested DS

	template <int, class T> typename enable_if<!needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) { return {ts(v)}; }
	template <int lev, class T> typename enable_if<needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) {
		if (lev == 0 || !(int)v.size()) return {ts(v)};
		vector<string> res;
		for (const auto& t : v) {
			if ((int)res.size()) res.back() += ",";
			vector<string> tmp = ts_lev<lev - 1>(t);
			res.insert(res.end(), tmp.begin(), tmp.end()); 
		}
		for (int i = 0; i < (int)res.size(); ++i) {
			string bef = " "; if (i == 0) bef = "{";
			res[i] = bef + res[i];
		}
		res.back() += "}";
		return res;
	}
}

inline namespace Output {
	template <class T> void pr_sep(ostream& os, string, const T& t) { os << ts(t); }
	template <class T, class... U> void pr_sep(ostream& os, string sep, const T& t, const U&... u) {
		pr_sep(os, sep, t); os << sep; pr_sep(os, sep, u...); }
	// print w/ no spaces

	template <class... T> void pr(const T&... t) { pr_sep(cout, "", t...); } 
	// print w/ spaces, end with newline

	void ps() { cout << "\n"; }
	template <class... T> void ps(const T&... t) { pr_sep(cout, " ", t...); ps(); } 
	// debug to cerr

	template <class... T> void dbg_out(const T&... t) {
		pr_sep(cerr, " | ", t...); cerr << endl; }
	void loc_info(int line, string names) {
		cerr << "Line(" << line << ") -> [" << names << "]: "; }
	template <int lev, class T> void dbgl_out(const T& t) {
		cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl; }
	#ifdef LOCAL
		#define dbg(...) loc_info(__LINE__, #__VA_ARGS__), dbg_out(__VA_ARGS__)
		#define dbgl(lev, x) loc_info(__LINE__, #x), dbgl_out<lev>(x)
	#else // don't actually submit with this
		#define dbg(...) 0
		#define dbgl(lev, x) 0
	#endif
}

inline namespace FileIO {
	void set_in(string s)  { (void)!freopen(s.c_str(), "r", stdin); }
	void set_out(string s) { (void)!freopen(s.c_str(), "w", stdout); }
	void set_io(string s = "") {
		cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams

		// cin.exceptions(cin.failbit);

		// throws exception when do smth illegal

		// ex. try to read letter into int

		if (!s.empty()) set_in(s + ".in"), set_out(s + ".out"); // for old USACO

	}
}

const int MOD = 1e9 + 7; // 998244353


typedef std::decay<decltype(MOD)>::type mod_t; 
struct mi {
	mod_t v;
	explicit operator mod_t() const { return v; }
	explicit operator bool() const { return v != 0; }
	mi() { v = 0; }
	mi(const long long& _v) {
		v = (-MOD <= _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD; }
	friend std::istream& operator>>(std::istream& in, mi& a) { 
		long long x; std::cin >> x; a = mi(x); return in; }
	friend std::ostream& operator<<(std::ostream& os, const mi& a) { return os << a.v; }
	friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }    
	friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
	friend bool operator>(const mi& a, const mi& b) { return a.v > b.v; }
	friend bool operator<=(const mi& a, const mi& b) { return a.v <= b.v; }
	friend bool operator>=(const mi& a, const mi& b) { return a.v >= b.v; }
	mi operator-() const { return mi(-v); }
	mi& operator+=(const mi& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this; }
	mi& operator-=(const mi& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this; }
	mi& operator*=(const mi& m) { v = (long long)v * m.v % MOD;
		return *this; }
	friend mi pow(mi a, long long p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; }
	friend mi inv(const mi& a) { assert(a != 0); return pow(a, MOD - 2); }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
};

const ld PI = acos((ld)-1);

typedef pair<mi, mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;

struct CentroidDecomposition {
	int n;
	std::vector<std::vector<int>> g, cg; // cg is directed tree for centroids

	std::vector<bool> vis;
	std::vector<int> size;
	std::vector<int> parent;
	int root;

	void init(int n_) {
		n = n_;
		g.assign(n, std::vector<int>());
		cg.assign(n, std::vector<int>());
		vis.assign(n, false);
		parent.assign(n, 0);
		size.assign(n, 0);
	}

	void ae(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}

	void dfs_size(int src, int par = -1) {
		size[src] = 1;
		for (int nxt : g[src]) {
			if (nxt == par || vis[nxt]) 
				continue;
			dfs_size(nxt, src);
			size[src] += size[nxt];
		}
	}

	int get_centroid(int src) {
		dfs_size(src);
		int num = size[src];
		int par = -1;
		do {    	
			int go = -1;
			for (int nxt : g[src]) {
				if (nxt == par || vis[nxt])
					continue;
				if (2 * size[nxt] > num) 
					go = nxt;
			}
			par = src;
			src = go;
		} while (src != -1);
		return par;
	}

	int build_dfs(int src, int par = -1) {
		int c = get_centroid(src);
		vis[c] = true;
		parent[c] = par;
		if (par != -1) {
			cg[par].push_back(c);
		}
		for (int nxt : g[c]) {
			if (vis[nxt]) 
				continue;
			build_dfs(nxt, c);
		}
		return c;
	}

	void build() {
		root = build_dfs(0);
	}
};  


template <class T> struct SparseTable {
	std::vector<T> v;
	std::vector<std::vector<int>> jump;

	int level(int x) { return 31 - __builtin_clz(x); }

	int comb(int a, int b) {
		return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
	}

	void init(const std::vector<T>& _v) {
		v = _v;
		jump = {std::vector<int>((int)v.size())};
		iota(jump[0].begin(), jump[0].end(), 0);
		for (int j = 1; (1 << j) <= (int)v.size(); j++) {
			jump.push_back(std::vector<int>((int)v.size() - (1 << j) + 1));
			for (int i = 0; i < (int)jump[j].size(); i++) {
				jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int index(int l, int r) {
		assert(l <= r);
		int d = level(r - l + 1);
		return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
	}

	T query(int l, int r) {
		return v[index(l, r)];
	}
};

struct LCARMQ {
	int n; 
	std::vector<std::vector<int>> adj;
	std::vector<int> dep, in, par, rev, out, pos;
	std::vector<std::pair<int, int>> tmp;
	SparseTable<std::pair<int, int>> S;
	std::vector<std::vector<int>> sparse;
	int ti = 0;

	void init(int _n) {
		n = _n;
		adj.resize(n);
		dep = in = out = par = rev = pos = std::vector<int>(n);
		sparse = {std::vector<int>(n)};
		for (int j = 1; (1 << j) <= n; j++) {
			sparse.push_back(std::vector<int>(n - (1 << j) + 1));
		}
	}

	void ae(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void dfs(int src) {
		in[src] = ti++;
		sparse[0][in[src]] = src;
		pos[src] = (int)tmp.size();
		tmp.emplace_back(dep[src], src);
		for (auto &nxt : adj[src]) {
			if (nxt == par[src]) continue;
			dep[nxt] = dep[par[nxt] = src] + 1;
			dfs(nxt);
			tmp.emplace_back(dep[src], src);
		}
		out[src] = ti;
	}

	inline int mini(int u, int v) {
		return (dep[u] < dep[v] || (dep[u] == dep[v] && in[u] > in[v])) ? u : v;
	}

	void gen(int root = 0) {
		par[root] = root;
		dfs(root);
		S.init(tmp); 
		for (int j = 1; j < (int)sparse.size(); j++) {
			for (int i = 0; i < (int)sparse[j].size(); i++) {
				sparse[j][i] = mini(sparse[j - 1][i], sparse[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	int lca(int u, int v) {
		u = pos[u];
		v = pos[v];
		if (u > v) std::swap(u, v);
		return S.query(u, v).second;
	}

	int dist(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}

	bool is_ancestor(int anc, int src) {
		return in[anc] <= in[src] && out[anc] >= out[src];
	}

	int get_child(int anc, int src) {
		if (!is_ancestor(anc, src)) return -1;
		int l = in[anc] + 1;
		int r = in[src];
		int d = 31 - __builtin_clz(r - l + 1);
		return mini(sparse[d][l], sparse[d][r - (1 << d) + 1]);
	}
	
	std::vector<std::pair<int, int>> compress(std::vector<int> nodes) {
		auto cmp = [&](int a, int b) {
			return pos[a] < pos[b];
		};
		sort(nodes.begin(), nodes.end(), cmp);
		for (int i = (int)nodes.size() - 2; i >= 0; i--) {
			nodes.push_back(lca(nodes[i], nodes[i + 1]));
		}
		sort(nodes.begin(), nodes.end(), cmp);
		nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
		std::vector<std::pair<int, int>> ret{{0, nodes[0]}};
		for (int i = 0; i < (int)nodes.size(); i++) {
			rev[nodes[i]] = i;
		}
		for (int i = 1; i < (int)nodes.size(); i++) {
			ret.emplace_back(rev[lca(nodes[i - 1], nodes[i])], nodes[i]);
		}
		return ret;
	}
};


// 5 is a root of both mods

template <int MOD, int RT> struct Mint {
	static const int mod = MOD;
	static constexpr Mint rt() { return RT; } // primitive root for FFT

	static constexpr int md() { return MOD; } // primitive root for FFT

	int v; 
	explicit operator int() const { return v; } // explicit -> don't silently convert to int

	explicit operator bool() const { return v != 0; }
	Mint() { v = 0; }
	Mint(long long _v) { v = int((-MOD <= _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.v == b.v; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.v < b.v; }
	friend bool operator>(const Mint& a, const Mint& b) { return a.v > b.v; }
	friend bool operator<=(const Mint& a, const Mint& b) { return a.v <= b.v; }
	friend bool operator>=(const Mint& a, const Mint& b) { return a.v >= b.v; }
	friend std::istream& operator >> (std::istream& in, Mint& a) { 
		long long x; std::cin >> x; a = Mint(x); return in; }
	friend std::ostream& operator << (std::ostream& os, const Mint& a) { return os << a.v; }
	Mint& operator+=(const Mint& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	Mint& operator-=(const Mint& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	Mint& operator*=(const Mint& m) { 
		v = (long long)v * m.v % MOD; return *this; }
	Mint& operator/=(const Mint& m) { return (*this) *= inv(m); }
	friend Mint pow(Mint a, long long p) {
		Mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; 
	}
	friend Mint inv(const Mint& a) { assert(a.v != 0); return pow(a, MOD - 2); }
	Mint operator-() const { return Mint(-v); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
};

namespace FFT {

template <class T> void fft(std::vector<T>& A, bool inv = 0) {
	int n = (int)A.size();
	assert((T::mod - 1) % n == 0);
	std::vector<T> B(n);
	for (int b = n / 2; b; b /= 2, A.swap(B)) {
		T w = pow(T::rt(), (T::mod - 1) / n * b);
		T m = 1;
		for (int i = 0; i < n; i += b * 2, m *= w)
			for (int j = 0; j < b; j++) {
				T u = A[i + j];
				T v = A[i + j + b] * m;
				B[i / 2 + j] = u + v;
				B[i / 2 + j + n / 2] = u - v;
			}
	}
	if (inv) {
		std::reverse(1 + A.begin(), A.end());
		T z = T(1) / T(n);
		for (auto& t : A) 
			t *= z;
	}
}

template <class T> std::vector<T> multiply(std::vector<T> A, std::vector<T> B) {
	int sa = (int)A.size();
	int sb = (int)B.size();
	if (!std::min(sa, sb))
		return {};
	int s = sa + sb - 1;
	int n = 1;
	for (; n < s; n *= 2);
	bool eq = A == B;
	A.resize(n);
	fft(A);
	if (eq) 
		B = A;
	else 
		B.resize(n), fft(B);
	for (int i = 0; i < n; i++)
		A[i] *= B[i];
	fft(A, 1);
	A.resize(s);
	return A;
}

template <class M, class T> std::vector<M> multiply_mod(std::vector<T> x, std::vector<T> y) {
	auto convert = [](const std::vector<T>& v) {
		std::vector<M> w((int)v.size());
		for (int i =  0; i < (int)v.size(); i++)
			w[i] = (int)v[i];
		return w;
	};
	return multiply(convert(x), convert(y));
}

template <class T> std::vector<T> general_multiply(const std::vector<T>& A, const std::vector<T>& B) { 
	// arbitrary modulus

	using m0 = Mint<(119 << 23) + 1, 62>; 
	using m1 = Mint<(5 << 25) + 1, 62>;
	using m2 = Mint<(7 << 26) + 1, 62>;
	auto c0 = multiply_mod<m0>(A, B);
	auto c1 = multiply_mod<m1>(A, B);
	auto c2 = multiply_mod<m2>(A, B);
	int n = (int)c0.size();
	std::vector<T> res(n);
	m1 r01 = 1 / m1(m0::mod);
	m2 r02 = 1 / m2(m0::mod);
	m2 r12 = 1 / m2(m1::mod);
	for (int i = 0; i < n; i++) {
		int a = c0[i].v;
		int b = ((c1[i] - a) * r01).v;
		int c = (((c2[i] - a) * r02 - b) * r12).v;
		res[i] = (T(c) * m1::mod + b) * m0::mod + a;
	}
	return res;
}

} // namespace FFT


namespace Polynomial {

using T = long long;
using Poly = std::vector<T>;

T eval(const Poly& p, const T& x) {
	T res = 0;
	for (int i = (int)p.size() - 1; i >= 0; --i) {
		res = x * res + p[i];
	}
	return res;
}

Poly& operator+=(Poly& l, const Poly& r) {
	l.resize(std::max((int)l.size(), (int)r.size()));
	for (int i = 0; i < (int)r.size(); ++i) {
		l[i] += r[i];
	}
	return l;
}

Poly& operator-=(Poly& l, const Poly& r) {
	l.resize(std::max((int)l.size(), (int)r.size()));
	for (int i = 0; i < (int)r.size(); ++i) {
		l[i] -= r[i];
	}
	return l;
}

Poly& operator*=(Poly& l, const T& r) {
	for (int i = 0; i < (int)l.size(); ++i) {
		l[i] *= r;
	}
	return l;
}

Poly& operator/=(Poly& l, const T& r) {
	for (int i = 0; i < (int)l.size(); ++i) {
		l[i] /= r;
	}
	return l;
}

Poly operator*(const Poly& l, const Poly& r) {
	if (!std::min((int)l.size(), (int)r.size())) {
		return {};
	}
	return FFT::general_multiply(l, r);
	Poly res((int)l.size() + (int)r.size() - 1);
	for (int i = 0; i < (int)l.size(); ++i) {
		for (int j = 0; j < (int)r.size(); ++j) {
			res[i + j] += l[i] * r[j];
		}
	}
	return res;
}

Poly operator+(Poly l, const Poly& r) { return l += r; }
Poly operator-(Poly l, const Poly& r) { return l -= r; }
Poly operator-(Poly l) { for (auto &t : l) t *= -1; return l; }
Poly operator*(Poly l, const T& r) { return l *= r; }
Poly operator*(const T& r, const Poly& l) { return l * r; }
Poly operator/(Poly l, const T& r) { return l /= r;	}
Poly& operator*=(Poly& l, const Poly& r) { return l = l * r; }

Poly derivative(const Poly& p) {
	Poly res;
	for (int i = 1; i < (int)p.size(); ++i) {
		res.push_back(T(i) * p[i]);
	}
	return res;
}

Poly integral(const Poly& p) {
	static Poly invs{0, 1};
	for (int i = invs.size(); i <= (int)p.size(); ++i ){
		invs.push_back(1 / T(i));
	}
	Poly res((int)p.size() + 1);
	for (int i = 0; i < (int)p.size(); ++i) {
		res[i + 1] = p[i] * invs[i + 1];
	}
	return res;
}

}

int main() {
	using namespace FFT;
	using namespace Polynomial;
	set_io("");
	int n;
	re(n);
	CentroidDecomposition cd;
	cd.init(n);
	LCARMQ lca;
	lca.init(n);
	vector<vi> g(n);
	f0r(i, n - 1) {
		int u, v;
		re(u, v);
		g[u].pb(v);
		g[v].pb(u);
		lca.ae(u, v);
		cd.ae(u, v);
	}
	lca.gen();
	cd.build();
	vl ans(n);
	function<vi(int)> dfs = [&](int u) { // return how many at dist x

		vi verts;
		vector<vl> polys;
		polys.pb({1});
		vl tmp;
		each(v, cd.cg[u]) {	
			auto res = dfs(v);
			each(x, res) verts.pb(x);
			tmp.assign(res.size() + 1, 0);
			each(x, res) {
				++tmp[lca.dist(x, u)];
			}
			while (tmp.back() == 0) tmp.pop_back();
			polys.pb(tmp);
		}	
		vl sum;
		each(x, polys) sum += x;
		vl res = sum * sum;
		each(x, polys) res -= x * x;
		res /= 2;
		f0r(i, sz(res)) {
			ans[i] += res[i];
		}
		verts.pb(u);
		return verts;
	};
	dfs(cd.root);
	f1r(i, 1, n) {
		pr(ans[i], ' ');
	}
	ps();
	return 0;
}

Back to top page