96712024-02-23 21:57:18999Átvágás (75 pont)cpp17Accepted 75/75238ms30256 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;
}
SubtaskSumTestVerdictTimeMemory
base75/75
1Accepted0/03ms1808 KiB
2Accepted0/03ms2056 KiB
3Accepted0/09ms3268 KiB
4Accepted4/43ms2332 KiB
5Accepted4/43ms2428 KiB
6Accepted4/43ms2536 KiB
7Accepted4/43ms2764 KiB
8Accepted4/43ms2864 KiB
9Accepted4/43ms2960 KiB
10Accepted4/4146ms29816 KiB
11Accepted4/4168ms29348 KiB
12Accepted4/4195ms30256 KiB
13Accepted4/4186ms30156 KiB
14Accepted4/4209ms28988 KiB
15Accepted4/4211ms27556 KiB
16Accepted4/4236ms27392 KiB
17Accepted4/4229ms27592 KiB
18Accepted5/5232ms27884 KiB
19Accepted6/6238ms27876 KiB
20Accepted6/6225ms27760 KiB
21Accepted2/23ms4328 KiB