187592025-11-04 17:04:35algoproFire on a Treecpp17Időlimit túllépés 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";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms5108 KiB
2Elfogadva4ms4916 KiB
subtask235/35
3Elfogadva6ms4916 KiB
4Elfogadva6ms4916 KiB
5Elfogadva4ms5000 KiB
6Elfogadva6ms4916 KiB
7Elfogadva4ms5116 KiB
subtask325/25
8Elfogadva7ms4944 KiB
9Elfogadva35ms5212 KiB
10Elfogadva96ms5336 KiB
11Elfogadva48ms5208 KiB
12Elfogadva68ms5208 KiB
13Elfogadva54ms5172 KiB
subtask40/40
14Időlimit túllépés1.082s9268 KiB
15Időlimit túllépés1.082s10960 KiB
16Időlimit túllépés1.083s25396 KiB
17Időlimit túllépés1.082s12460 KiB
18Időlimit túllépés1.082s11572 KiB
19Időlimit túllépés1.082s12092 KiB
20Időlimit túllépés1.082s12584 KiB
21Időlimit túllépés1.083s12340 KiB
22Időlimit túllépés1.075s12092 KiB