?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
187566241 |
Practice: DaiRuiChen007 |
1646D - 42 | C++14 (GCC 6-32) | Accepted | 233 ms | 26692 KB | 2023-01-02 01:57:12 | 2023-01-02 01:57:12 |
// LUOGU_RID: 98468657 #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+1; vector <int> G[MAXN]; int val[MAXN]; struct node { int cnt,val; node(int _cnt,int _val) { cnt=_cnt,val=_val; } node() { node(0,0); } inline friend bool operator <(const node &A,const node &B) { if(A.cnt==B.cnt) return A.val<B.val; return A.cnt>B.cnt; } inline friend node operator +(const node &A,const node &B) { return node(A.cnt+B.cnt,A.val+B.val); } } dp[MAXN][2]; inline node _min(const node &A,const node &B) { return A<B?A:B; } inline void dfs(int p,int f) { dp[p][0]=node(0,1); dp[p][1]=node(1,(int)G[p].size()); for(int v:G[p]) { if(v==f) continue; dfs(v,p); dp[p][0]=dp[p][0]+_min(dp[v][0],dp[v][1]); dp[p][1]=dp[p][1]+dp[v][0]; } } inline void print(int p,int f,int col) { val[p]=col==1?G[p].size():1; for(int v:G[p]) { if(v==f) continue; if(col==1) print(v,p,0); else print(v,p,dp[v][0]<dp[v][1]?0:1); } } signed main() { int n; scanf("%d",&n); for(int i=1;i<n;++i) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } if(n==2) { puts("2 2"); puts("1 1"); return 0; } dfs(1,0); print(1,0,dp[1][0]<dp[1][1]?0:1); printf("%d %d\n",_min(dp[1][0],dp[1][1]).cnt,_min(dp[1][0],dp[1][1]).val); for(int i=1;i<=n;++i) printf("%d ",val[i]); puts(""); return 0; }
?
?
?
?