제출 #1277297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277297		julia_08	Hard route (IZhO17_road)	C++20	100 / 100	553 ms	144788 KiB

road

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 5e5 + 10;

pair<ll, ll> dp_1[MAXN], dp_2[MAXN];

vector<int> adj[MAXN];

pair<ll, ll> ans;

void dfs_1(int v, int p){
  
  dp_1[v] = {-1e9, 0};
  
  if(adj[v].size() == 1) dp_1[v] = {0, 1};

  for(auto u : adj[v]){
    if(u != p){
      
      dfs_1(u, v);
      
      if(dp_1[u].first + 1 > dp_1[v].first){
        dp_1[v] = {dp_1[u].first + 1, dp_1[u].second};
      } else if(dp_1[u].first + 1 == dp_1[v].first) dp_1[v].second += dp_1[u].second;
      
    }
  }
  
  // cout << v << " -> " << dp_1[v].first << " " << dp_1[v].second << endl;

}

void dfs_2(int v, int p){
  
  // cout << v << " -> " << dp_2[v].first << " " << dp_2[v].second << endl;

  map<ll, ll> freq;
  
  for(auto u : adj[v]){
    if(u != p){
      freq[dp_1[u].first + 1] += dp_1[u].second;
    }
  }

  for(auto u : adj[v]){
    if(u != p){
      
      dp_2[u] = {dp_2[v].first + 1, dp_2[v].second};
      
      freq[dp_1[u].first + 1] -= dp_1[u].second;
      
      if(freq[dp_1[u].first + 1] == 0) freq.erase(dp_1[u].first + 1);
    
      if(!freq.empty()){
        
        auto [d, cnt] = *freq.rbegin();
        
        if(d + 1 > dp_2[u].first){
          dp_2[u] = {d + 1, cnt};
        } else if(d + 1 == dp_2[u].first) dp_2[u].second += cnt;
        
      }
      
      freq[dp_1[u].first + 1] += dp_1[u].second;
    
    }
  }
  
  freq.clear();
  
  for(auto u : adj[v]) if(u != p) dfs_2(u, v);

}

void dfs_3(int v, int p){
  
  for(auto u : adj[v]) if(u != p) dfs_3(u, v);
  
  vector<pair<ll, ll>> choices;
  
  for(auto u : adj[v]){
    if(u != p){
      choices.push_back({dp_1[u].first + 1, dp_1[u].second});
    }
  }
  
  choices.push_back(dp_2[v]);

  if(choices.size() < 3) return;
  
  sort(choices.rbegin(), choices.rend());
  
  pair<ll, ll> cur = {0, 0};

  ll a = choices[0].first, b = choices[1].first, c = choices[2].first;
  
  cur.first = a * (b + c);
  
  if(a == b && b == c){
    
    ll tot = 0;
    
    for(auto [x, cnt] : choices) if(x == a) tot += cnt;
    
    for(auto [x, cnt] : choices){
      if(x == a){
        cur.second += cnt * (tot - cnt);
      }
    }
    
    cur.second /= 2;
    
  } else if(a == b){
    
    ll tot_b = 0, tot_c = 0;
    
    for(auto [x, cnt] : choices){
      if(x == b) tot_b += cnt;
      if(x == c) tot_c += cnt;
    }
    
    cur.second += tot_b * tot_c;
    
  } else if(b == c){
    
    ll tot = 0;
    
    for(auto [x, cnt] : choices) if(x == b) tot += cnt;
    
    for(auto [x, cnt] : choices){
      if(x == b){
        cur.second += cnt * (tot - cnt);
      }
    }
    
    cur.second /= 2;
    
  } else{
    
    ll tot_b = 0, tot_c = 0;
    
    for(auto [x, cnt] : choices){
      if(x == b) tot_b += cnt;
      if(x == c) tot_c += cnt;
    }
    
    cur.second += tot_b * tot_c;
    
  }
  
  if(cur.first > ans.first){
    ans = cur;
  } else if(cur.first == ans.first) ans.second += cur.second;

}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  
  int n; cin >> n;
  
  for(int i=1; i<=n; i++) dp_2[i] = {-1e9, 0};

  for(int i=1; i<n; i++){
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs_1(1, 1);

  if(adj[1].size() == 1) dp_2[1] = {0, 1};

  dfs_2(1, 1);
  
  ans = {0, 0};

  dfs_3(1, 1);
  
  ll leaves = 0;
  
  for(int i=1; i<=n; i++) leaves += (adj[i].size() == 1);

  if(ans.first == 0) ans.second = (leaves * (leaves - 1)) / 2;

  cout << ans.first << " " << ans.second << "\n";

  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48