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