9671 | 2024. 02. 23 21:57:18 | 999 | Átvágás (75 pont) | cpp17 | Elfogadva 75/75 | 238ms | 30256 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;cin>>n;
vector<vector<int>> v(n+1);
for(int i = 0;i<n-1;i++){
int a,b;cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> fok(n+1,-1);
int ans1=0, ans2=0;
queue<int> q;
int k=1;
while(v[k].size()!=1)k++;
q.push(k);
fok[k]=0;
while(!q.empty()){
int node=q.front();
q.pop();
if(node!=k&&v[node].size()>2)ans1+=(int)v[node].size()-2;
for(int i : v[node]){
if(fok[i]==-1){
q.push(i);
fok[i]=v[i].size();
}
}
}
int temp=1;
for(int i = 1;i<=n;i++){
if(fok[temp]<fok[i])temp=i;
}
fill(fok.begin(),fok.end(),-1);
q.push(temp);
fok[temp]=0;
while(!q.empty()){
int node=q.front();
q.pop();
bool corr=false;
for(int i : v[node]){
if(i==temp)corr=true;
if(fok[i]==-1){
q.push(i);
fok[i]=v[i].size();
}
}
if(!corr&&node!=temp)ans2++;
}
cout<<ans1<<' '<<ans2<<endl;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 75/75 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2056 KiB | |||
3 | Elfogadva | 0/0 | 9ms | 3268 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2332 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2428 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2536 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2764 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 2864 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 2960 KiB | |||
10 | Elfogadva | 4/4 | 146ms | 29816 KiB | |||
11 | Elfogadva | 4/4 | 168ms | 29348 KiB | |||
12 | Elfogadva | 4/4 | 195ms | 30256 KiB | |||
13 | Elfogadva | 4/4 | 186ms | 30156 KiB | |||
14 | Elfogadva | 4/4 | 209ms | 28988 KiB | |||
15 | Elfogadva | 4/4 | 211ms | 27556 KiB | |||
16 | Elfogadva | 4/4 | 236ms | 27392 KiB | |||
17 | Elfogadva | 4/4 | 229ms | 27592 KiB | |||
18 | Elfogadva | 5/5 | 232ms | 27884 KiB | |||
19 | Elfogadva | 6/6 | 238ms | 27876 KiB | |||
20 | Elfogadva | 6/6 | 225ms | 27760 KiB | |||
21 | Elfogadva | 2/2 | 3ms | 4328 KiB |