部分木の大きさ
(graph_tree/child_size.hpp)

#pragma once
#include<vector>
#include<cmath>
#include"graph_template.hpp"

/**
 * @brief 部分木の大きさ
 */

std::vector<int> child_size(int start,const graph& g){
	std::vector<int>memo(g.size());
	auto f=[&](auto f,int v,int p)->int{
		T res=0;
		for(auto t:g[v]){
			if(t==p)continue;
			res+=f(f,t,v);
		}
		return memo[v]=res+1;
	};
	f(f,start,-1);
	return memo;
}

#line 2 "graph_tree/child_size.hpp"
#include<vector>
#include<cmath>
#line 3 "graph_tree/graph_template.hpp"
#include<tuple>
#include<iostream>
/**
 * @brief グラフテンプレート
 */

using graph=std::vector<std::vector<int>>;
template<typename T>
using graph_w=std::vector<std::vector<std::pair<int,T>>>;

graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;}
graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;}
graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;}
template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;}
#line 5 "graph_tree/child_size.hpp"

/**
 * @brief 部分木の大きさ
 */

std::vector<int> child_size(int start,const graph& g){
	std::vector<int>memo(g.size());
	auto f=[&](auto f,int v,int p)->int{
		T res=0;
		for(auto t:g[v]){
			if(t==p)continue;
			res+=f(f,t,v);
		}
		return memo[v]=res+1;
	};
	f(f,start,-1);
	return memo;
}