AT220F

​​​​​​题目传送门

思路

假设我们已经知道了一个节点它的答案，于是可以求与它有连边的点，的所有子树节点的距离都被减小了1，而除此之外的节点距离都被增大了1，如果表示答案，表示子树大小，则有

于是考虑从1出发，求出1的答案，然后从1出发再做一次dfs，求出相邻的节点，然后一直求完。

代码

#include
#define int long long
using namespace std;
int n,ans[200001],s[200001];
vectorg[200001];
void dfs(int x,int f,int len){
	ans[1]+=len;
	for(int v:g[x])
		if(f!=v){
			dfs(v,x,len+1);
			s[x]+=s[v];
		}
	++s[x];
}
void Dfs(int x,int f){
	ans[x]=ans[f]+n-s[x]-s[x];
	for(int v:g[x])
		if(f!=v)
			Dfs(v,x);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0,0);
	for(int v:g[1])
		Dfs(v,1);
    for(int i=1;i<=n;++i)
        cout<