| 18756 | 2025-11-04 17:00:25 | algopro | Fire on a Tree | cpp17 | Wrong answer 0/100 | 239ms | 40536 KiB |
// UUID: 7fdef4db-a270-4cd7-9975-5fdff3603539
#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);
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1; i<=n; i++)
cout<<ans[i]<<" ";
cout<<"\n";
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 4ms | 4916 KiB | ||||
| 2 | Accepted | 4ms | 5100 KiB | ||||
| subtask2 | 0/35 | ||||||
| 3 | Wrong answer | 6ms | 5136 KiB | ||||
| 4 | Wrong answer | 4ms | 4984 KiB | ||||
| 5 | Accepted | 4ms | 5136 KiB | ||||
| 6 | Wrong answer | 6ms | 4916 KiB | ||||
| 7 | Wrong answer | 4ms | 4916 KiB | ||||
| subtask3 | 0/25 | ||||||
| 8 | Wrong answer | 6ms | 4916 KiB | ||||
| 9 | Wrong answer | 6ms | 5172 KiB | ||||
| 10 | Accepted | 6ms | 5428 KiB | ||||
| 11 | Wrong answer | 7ms | 5368 KiB | ||||
| 12 | Wrong answer | 6ms | 5356 KiB | ||||
| 13 | Wrong answer | 6ms | 5172 KiB | ||||
| subtask4 | 0/40 | ||||||
| 14 | Wrong answer | 103ms | 9808 KiB | ||||
| 15 | Wrong answer | 143ms | 12220 KiB | ||||
| 16 | Accepted | 190ms | 40536 KiB | ||||
| 17 | Wrong answer | 236ms | 14124 KiB | ||||
| 18 | Wrong answer | 238ms | 12852 KiB | ||||
| 19 | Wrong answer | 197ms | 13300 KiB | ||||
| 20 | Wrong answer | 196ms | 14128 KiB | ||||
| 21 | Wrong answer | 239ms | 13540 KiB | ||||
| 22 | Wrong answer | 172ms | 13120 KiB | ||||