?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
188209166 |
Practice: DaiRuiChen007 |
1566E - 35 | C++14 (GCC 6-32) | Accepted | 140 ms | 8540 KB | 2023-01-06 15:10:25 | 2023-01-06 15:10:25 |
// LUOGU_RID: 98856294 #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+1; int cnt=0; vector <int> G[MAXN]; inline bool dfs(int p,int f) { if(f!=0&&G[p].size()==1) return false; bool ret=false; for(int v:G[p]) { if(v==f) continue; ret|=!dfs(v,p); } if(ret&&f!=0) ++cnt; return ret; } inline void solve() { int n; scanf("%d",&n); for(int i=1;i<=n;++i) G[i].clear(); 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); } cnt=0; bool ret=dfs(1,0); if(!ret) printf("%d\n",n-2*cnt); else printf("%d\n",n-2*cnt-1); } signed main() { int T; scanf("%d",&T); while(T--) solve(); return 0; }
?
?
?
?