library
This documentation is automatically generated by online-judge-tools/verification-helper
Verify/LC_frequency_table_of_tree_distance.test.cpp
- View this file on GitHub
- Last update: 2024-04-26 03:18:17+09:00
- Problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance
Depends on
- Fast Fourier Transform
(Convolution/fft.hpp)
- Centroid Decomposition
(Graph/centroid.hpp)
- Template/template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"
#include "Template/template.hpp"
#include "Convolution/fft.hpp"
#include "Graph/centroid.hpp"
int main(){
int n;
cin>>n;
CentroidDecomposition cd(n);
rep(i,0,n-1){
int x,y;
cin>>x>>y;
cd.add_edge(x,y);
}
vector<ll> ret(n);
auto rec=[&](auto& _rec,int rt)->void{
int cen=cd.find(rt);
for(auto& to:cd.g[cen])if(!cd.used[to])_rec(_rec,to);
vector<ll> sum,cur;
auto dfs=[&](auto& f,int v,int p,int d)->void{
if((int)cur.size()<=d)cur.resize(d+1);
cur[d]++;
for(auto& to:cd.g[v])if(to!=p and !cd.used[to])f(f,to,v,d+1);
};
for(auto& to:cd.g[cen])if(!cd.used[to]){
cur.clear();
dfs(dfs,to,cen,1);
auto sub=FFT::square(cur);
rep(i,0,min((int)sub.size(),n))ret[i]-=sub[i];
if(sum.size()<cur.size())sum.resize(cur.size());
rep(i,0,cur.size())sum[i]+=cur[i];
}
rep(i,0,min((int)sum.size(),n))ret[i]+=sum[i]*2;
auto add=FFT::square(sum);
rep(i,0,min((int)add.size(),n))ret[i]+=add[i];
cd.used[cen]=0;
};
rec(rec,0);
rep(i,1,n){
ret[i]>>=1;
cout<<ret[i]<<'\n';
}
return 0;
}#line 1 "Verify/LC_frequency_table_of_tree_distance.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"
#line 1 "Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b-1); i >= (int)(a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template <typename T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <typename T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
template <typename T, typename U> T ceil(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U> T floor(T x, U y) {
assert(y != 0);
if (y < 0)
x = -x, y = -y;
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T> int popcnt(T x) {
return __builtin_popcountll(x);
}
template <typename T> int topbit(T x) {
return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <typename T> int lowbit(T x) {
return (x == 0 ? -1 : __builtin_ctzll(x));
}
#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
for (; a[i] != ',' && a[i] != '\0'; i++)
cerr << a[i];
cerr << ":" << b << " ";
_show(i + 1, a, c...);
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "P(" << p.first << ", " << p.second << ")";
return os;
}
template <typename T, template <class> class C>
ostream &operator<<(ostream &os, const C<T> &v) {
os << "[";
for (auto d : v)
os << d << ", ";
os << "]";
return os;
}
#line 2 "Convolution/fft.hpp"
namespace FFT{
struct C{
double x,y;
C(double _x=0,double _y=0):x(_x),y(_y){}
C operator~()const{return C(x,-y);}
C operator*(const C& c)const{return C(x*c.x-y*c.y,x*c.y+y*c.x);}
C operator+(const C& c)const{return C(x+c.x,y+c.y);}
C operator-(const C& c)const{return C(x-c.x,y-c.y);}
};
vector<vector<C>> w(1,vector<C>(1,1));
void init(int lg){
for(int d=1,m=1;d<=lg;d++,m<<=1)if(d>=(int)w.size()){
w.emplace_back(m);
const double th=M_PI/m;
for(int i=0;i<m;i++)w[d][i]=(i&1?C(cos(th*i),sin(th*i)):w[d-1][i>>1]);
}
}
void fft(vector<C>& f,bool inv){
const int n=f.size(); const int lg=__lg(n);
if(lg>=(int)w.size())init(lg);
if(inv){
for(int k=1;k<=lg;k++){
const int d=1<<(k-1);
for(int s=0;s<n;s+=2*d){
for(int i=s;i<s+d;i++){
C x=f[i],y=~w[k][i-s]*f[d+i];
f[i]=x+y; f[d+i]=x-y;
}
}
}
}
else{
for(int k=lg;k;k--){
const int d=1<<(k-1);
for(int s=0;s<n;s+=2*d){
for(int i=s;i<s+d;i++){
C x=f[i],y=f[d+i];
f[i]=x+y; f[d+i]=w[k][i-s]*(x-y);
}
}
}
}
}
template<typename T>vector<T> mult(const vector<T>& a,const vector<T>& b){
const int as=a.size(); const int bs=b.size();
if(!as or !bs)return {};
const int cs=as+bs-1; vector<T> c(cs);
if(max(as,bs)<16){
for(int i=0;i<as;i++)for(int j=0;j<bs;j++){
c[i+j]+=(int)a[i]*b[j];
}
return c;
}
const int n=1<<__lg(2*cs-1); vector<C> f(n);
for(int i=0;i<as;i++)f[i].x=a[i];
for(int i=0;i<bs;i++)f[i].y=b[i];
fft(f,0); static const C rad(0,-.25);
for(int i=0;i<n;i++){
int j=i?i^((1<<__lg(i))-1):0;
if(i>j)continue;
C x=f[i]+~f[j],y=f[i]-~f[j];
f[i]=x*y*rad; f[j]=~f[i];
}
fft(f,1); for(int i=0;i<cs;i++)c[i]=round(f[i].x/n);
return c;
}
template<typename T>vector<T> square(const vector<T>& a){
const int as=a.size(); if(!as)return {};
const int cs=as*2-1; vector<T> c(cs);
if(as<16){
for(int i=0;i<as;i++)for(int j=0;j<as;j++){
c[i+j]+=(int)a[i]*a[j];
}
return c;
}
const int n=1<<__lg(cs*2-1); vector<C> f(n);
for(int i=0;i<as;i++)f[i].x=a[i];
fft(f,0); for(int i=0;i<n;i++)f[i]=f[i]*f[i];
fft(f,1); for(int i=0;i<cs;i++)c[i]=round(f[i].x/n);
return c;
}
}
/**
* @brief Fast Fourier Transform
*/
#line 2 "Graph/centroid.hpp"
class CentroidDecomposition{
void get(int v,int p){
sz[v]=1;
for(auto& to:g[v])if(to!=p and !used[to]){
get(to,v);
sz[v]+=sz[to];
}
}
int dfs(int v,int p,int rt){
for(auto& to:g[v])if(to!=p and !used[to]){
if(sz[to]>(sz[rt]>>1))return dfs(to,v,rt);
}
return v;
}
public:
int n;
vector<vector<int>> g;
vector<int> sz,used;
CentroidDecomposition(int n_):n(n_),g(n),sz(n),used(n){}
void add_edge(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
int find(int rt){
get(rt,-1);
int res=dfs(rt,-1,rt);
used[res]=1;
return res;
}
};
/**
* @brief Centroid Decomposition
*/
#line 6 "Verify/LC_frequency_table_of_tree_distance.test.cpp"
int main(){
int n;
cin>>n;
CentroidDecomposition cd(n);
rep(i,0,n-1){
int x,y;
cin>>x>>y;
cd.add_edge(x,y);
}
vector<ll> ret(n);
auto rec=[&](auto& _rec,int rt)->void{
int cen=cd.find(rt);
for(auto& to:cd.g[cen])if(!cd.used[to])_rec(_rec,to);
vector<ll> sum,cur;
auto dfs=[&](auto& f,int v,int p,int d)->void{
if((int)cur.size()<=d)cur.resize(d+1);
cur[d]++;
for(auto& to:cd.g[v])if(to!=p and !cd.used[to])f(f,to,v,d+1);
};
for(auto& to:cd.g[cen])if(!cd.used[to]){
cur.clear();
dfs(dfs,to,cen,1);
auto sub=FFT::square(cur);
rep(i,0,min((int)sub.size(),n))ret[i]-=sub[i];
if(sum.size()<cur.size())sum.resize(cur.size());
rep(i,0,cur.size())sum[i]+=cur[i];
}
rep(i,0,min((int)sum.size(),n))ret[i]+=sum[i]*2;
auto add=FFT::square(sum);
rep(i,0,min((int)add.size(),n))ret[i]+=add[i];
cd.used[cen]=0;
};
rec(rec,0);
rep(i,1,n){
ret[i]>>=1;
cout<<ret[i]<<'\n';
}
return 0;
}