187592025-11-04 17:04:35algoproFire on a Treecpp17Time limit exceeded 60/1001.083s25396 KiB
// UUID: d1474b4f-e580-4b71-ac5f-941af679659b
#include <bits/stdc++.h>
using namespace std;
const int c=2e5+10;
vector<int> adj[c];
int dp[c];
void dfs1(int cs, int p)
{
	dp[cs]=1;
	int s=0,mx=0;
	for(int &i:adj[cs])
		if(i!=p)
		{
			dfs1(i,cs);
			s+=dp[i];
			mx=max(mx,dp[i]);
		}
	dp[cs]+=s-mx;
}
int ans[c];
void dfs2(int cs, int p, int ert)
{
	int s=ert,mx=ert;
	for(int &i:adj[cs])
		if(i!=p) s+=dp[i],mx=max(mx,dp[i]);
	ans[cs]=1+s-mx;
	vector<array<int, 2>> gy{{ert,p}};
	for(int &i:adj[cs])
		if(i!=p) gy.push_back({dp[i],i});
	sort(gy.rbegin(),gy.rend());
	for(int &i:adj[cs])
	{
		if(i==p) continue;
		int tmp=s+1;
		if(i==gy[0][1]) tmp-=gy[1][0];
		else tmp-=gy[0][0];
		dfs2(i,cs,tmp);
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	for(int i=1; i<n; i++)
	{
		int a,b; cin>>a>>b;
		a++,b++;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			dp[j]=0;
		dfs1(i,0);
		cout<<dp[i]<<" ";
	}
	cout<<"\n";
	exit(0);
	dfs1(1,0);
	dfs2(1,0,0);
	for(int i=1; i<=n; i++)
		cout<<ans[i]<<" ";
	cout<<"\n";

}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms5108 KiB
2Accepted4ms4916 KiB
subtask235/35
3Accepted6ms4916 KiB
4Accepted6ms4916 KiB
5Accepted4ms5000 KiB
6Accepted6ms4916 KiB
7Accepted4ms5116 KiB
subtask325/25
8Accepted7ms4944 KiB
9Accepted35ms5212 KiB
10Accepted96ms5336 KiB
11Accepted48ms5208 KiB
12Accepted68ms5208 KiB
13Accepted54ms5172 KiB
subtask40/40
14Time limit exceeded1.082s9268 KiB
15Time limit exceeded1.082s10960 KiB
16Time limit exceeded1.083s25396 KiB
17Time limit exceeded1.082s12460 KiB
18Time limit exceeded1.082s11572 KiB
19Time limit exceeded1.082s12092 KiB
20Time limit exceeded1.082s12584 KiB
21Time limit exceeded1.083s12340 KiB
22Time limit exceeded1.075s12092 KiB