| 18764 | 2025-11-04 17:08:45 | horka | Fire on a Tree | cpp17 | Elfogadva 100/100 | 256ms | 40608 KiB |
#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-dp[i];
if(i==gy[0][1]) tmp-=gy[1][0];
else tmp-=gy[0][0];
dfs2(i,cs,tmp+1);
}
}
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);
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1; i<=n; i++)
cout<<ans[i]<<" ";
cout<<"\n";
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 4ms | 4916 KiB | ||||
| 2 | Elfogadva | 6ms | 4916 KiB | ||||
| subtask2 | 35/35 | ||||||
| 3 | Elfogadva | 6ms | 5116 KiB | ||||
| 4 | Elfogadva | 4ms | 4976 KiB | ||||
| 5 | Elfogadva | 4ms | 4984 KiB | ||||
| 6 | Elfogadva | 4ms | 4964 KiB | ||||
| 7 | Elfogadva | 4ms | 4916 KiB | ||||
| subtask3 | 25/25 | ||||||
| 8 | Elfogadva | 4ms | 4916 KiB | ||||
| 9 | Elfogadva | 7ms | 5172 KiB | ||||
| 10 | Elfogadva | 7ms | 5428 KiB | ||||
| 11 | Elfogadva | 6ms | 5172 KiB | ||||
| 12 | Elfogadva | 7ms | 5172 KiB | ||||
| 13 | Elfogadva | 6ms | 5172 KiB | ||||
| subtask4 | 40/40 | ||||||
| 14 | Elfogadva | 127ms | 10036 KiB | ||||
| 15 | Elfogadva | 143ms | 12168 KiB | ||||
| 16 | Elfogadva | 193ms | 40608 KiB | ||||
| 17 | Elfogadva | 247ms | 14068 KiB | ||||
| 18 | Elfogadva | 234ms | 12792 KiB | ||||
| 19 | Elfogadva | 218ms | 13212 KiB | ||||
| 20 | Elfogadva | 206ms | 14204 KiB | ||||
| 21 | Elfogadva | 256ms | 13440 KiB | ||||
| 22 | Elfogadva | 202ms | 13148 KiB | ||||