提出 #73542789

---

ソースコード 拡げる

#include <bits/stdc++.h>
#ifndef LOCAL
#include <atcoder/all>
#endif
using namespace std;
using i64 = long long;
#define int i64
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j, k) for(int i = (j); i >= (k); i--)
#define pb emplace_back
#define fi first
#define se second
using vi = vector<int>;
using pi = pair<int, int>;

template<typename T0, typename T1> bool chmin(T0 &x, const T1 &y){
	if(y < x){x = y; return true;} return false;
}
template<typename T0, typename T1> bool chmax(T0 &x, const T1 &y){
	if(x < y){x = y; return true;} return false;
}

template<typename T> ostream& operator << (ostream& os, const vector<T> &vec){
	os << "[";
	for(size_t i = 0; i < vec.size(); i ++){
		if(i > 0) os << ", ";
		os << vec[i];
	}
	os << "]";
	return os;
}

template<typename T> void debug(char *s, T x){
	cerr << s <<" = "<< x <<endl;
}
template<typename T, typename ...Ar> void debug(char *s, T x, Ar... y){
	int dep = 0;
	while(!(*s == ',' && dep == 0)){
		if(*s == '(') dep++;
		if(*s == ')') dep--;
		cerr << *s++;
	}
	cerr <<" = "<< x <<",";
	debug(s + 1, y...);
}
#define gdb(...) debug((char*)#__VA_ARGS__, __VA_ARGS__)

vi conv(vi a, vi b){
	#ifdef LOCAL
	vi res(a.size() + b.size() - 1);
	rep(i, 0, int(a.size()) - 1){
		rep(j, 0, int(b.size()) - 1){
			res[i + j] += a[i] * b[j];
		}
	}
	return res;
	#else
	return atcoder::convolution_ll(a, b);
	#endif
}

signed main(){
	#ifdef LOCAL
	assert( freopen(".in", "r", stdin) );
	assert( freopen(".out", "w", stdout) );
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<vi> G(n);
	rep(i, 0, n - 2){
		int u, v;
		cin >> u >> v;
		u --, v --;
		G[u].pb(v);
		G[v].pb(u);
	}
	vi mnd(n, -1);
	{
		queue<int> Q;
		vi deg(n);
		rep(i, 0, n - 1){
			deg[i] = G[i].size();
		}
		rep(i, 0, n - 1){
			if(deg[i] <= 1){
				mnd[i] = 0;
				Q.emplace(i);
			}
		}
		while(Q.size()){
			int u = Q.front();
			Q.pop();
			deg[u] = 0;
			for(int v:G[u]){
				if(deg[v] >= 1){
					chmax(mnd[v], mnd[u] + 1);
					deg[v] --;
					if(deg[v] == 1){
						Q.emplace(v);
					}
				}
			}
		}
	}

	int R = -1;
	{
		auto chk = [&](int d){
			rep(u, 0, n - 1){
				int deg = 0;
				for(int v:G[u]){
					deg += (mnd[v] >= d);
				}
				if(deg > 2){
					return false;
				}
			}
			return true;
		};
		int l = 0, r = n;
		while(l + 1 < r){
			int mid = (l + r) / 2 - 1;
			if(chk(mid)){
				r = mid + 1;
			} else{
				l = mid + 1;
			}
		}
		R = l;
	}
	auto solve_dis = [&](int R){
		vi ok(n);
		rep(i, 0, n - 1){
			ok[i] = (mnd[i] >= R);
		}
		vi P;
		{
			int rt = -1;
			rep(u, 0, n - 1){
				if(!ok[u]){
					continue;
				}
				int deg = 0;
				for(int v:G[u]){
					deg += ok[v];
				}
				if(deg <= 1){
					rt = u;
				}
				if(deg > 2){
					return vi(n + 1, 0);
				}
			}
			assert(~rt);
			auto dfs = [&](auto &self, int u, int p)->void {
				P.pb(u);
				for(int v:G[u]){
					if(v != p && ok[v]){
						self(self, v, u);
					}
				}
			};
			dfs(dfs, rt, -1);
		}
		auto get_vec = [&](int u, int p)->vi {
			vi res;
			auto dfs = [&](auto &self, int u, int p, int d)->void {
				while(int(res.size()) <= d){
					res.pb(0);
				}
				res[d] ++;
				for(int v:G[u]){
					if(v != p){
						self(self, v, u, d + 1);
					}
				}
			};
			dfs(dfs, u, p, 0);
			return res;
		};

		vi ans(n * 2 + 1);
		if(P.size() == 1){
			int u = P[0];
			vi t = get_vec(u, -1);
			t = conv(t, t);
			rep(i, 0, int(t.size()) - 1){
				ans[i] += t[i];
			}
			for(int v:G[u]){
				vi t = get_vec(v, u);
				t.insert(t.begin(), 0);
				t = conv(t, t);
				rep(i, 0, int(t.size()) - 1){
					ans[i] -= t[i];
				}
			}
			ans[0] ++;
			rep(i, 0, int(ans.size()) - 1){
				ans[i] /= 2;
			}
		} else{
			vi a = get_vec(P[0], P[1]);
			vi b = get_vec(P.end()[-1], P.end()[-2]);
			vi c = conv(a, b);
			rep(i, 0, int(c.size()) - 1){
				ans[i] += c[i];
			}
		}
		vi res(n + 1);
		int len = P.size();
		rep(i, 1, n){
			res[i] = (i < len? 0: ans[i - len]);
		}
		return res;
	};
	vi ans0 = solve_dis(R);
	// vi ans1 = solve_dis(R - 1);
	rep(i, 1, n){
		cout << ans0[i] <<'\n';
	}
}

提出情報

ジャッジ結果