!外星人入侵了我的电脑,导致了ABC220F换根DP代码没过样例,求调
  • 板块灌水区
  • 楼主Zq_water
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/1 07:34
  • 上次更新2024/8/1 07:36:53
查看原帖
!外星人入侵了我的电脑,导致了ABC220F换根DP代码没过样例,求调
895435
Zq_water楼主2024/8/1 07:34
#include<bits/stdc++.h>
#define INF 1e16
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 2e5+5;

int n,cnt;
int head[N],siz[N],f[N],g[N];
struct Edge{int to,next;}edge[N<<1];
void add(int u,int v){edge[++cnt]={v,head[u]};head[u]=cnt;}

void dfs(int u,int fa){
	siz[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u),siz[u]+=siz[v];
		f[u]+=(f[v]+siz[v]);
	}
}
void dp(int u,int fa){
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		g[v]=g[u]-siz[v]+(n-siz[v]);
		dfs(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++)cin>>u>>v,add(u,v),add(v,u);
	dfs(1,0),g[1]=f[1],dp(1,0); 
	for(int i=1;i<=n;i++)cout<<g[i]<<endl;
	return 0;
}
2024/8/1 07:34
加载中...