제출 #758154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758154		vjudge1	Hard route (IZhO17_road)	C++17	52 / 100	322 ms	988 KiB

road

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e7+9;
const int N=5005;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

int n,ans,cnt;
int dis[N];
pair<int,int> lvs[N];
vector<int> v[N];


void cldis(int i,int par,int d) {
  dis[i]=0;
  for (int j:v[i]) {
    if (j!=par) {
      cldis(j,i,d+1);
      dis[i]=max(dis[i],dis[j]);
    }
  }
  dis[i]++;
}

void dfs(int i,int par,int lvl,int h) {
  if (v[i].size()==1 && par!=0) {
    int tmp=lvl*h;
    if (tmp==ans) cnt++;
    else if (tmp>ans) {ans=tmp; cnt=1;}
    return;
  }

  int mx1=0,mx2=0;
  for (int j:v[i]) {
    if (j!=par) {
      if (dis[j]>=mx1) {mx2=mx1; mx1=dis[j];}
      else if (dis[j]<mx1 && dis[j]>mx2) mx2=dis[j];
    }
  }

  for (int j:v[i]) {
    int gg;
    if (j!=par) {
      if (dis[j]==mx1) gg=mx2;
      else gg=mx1;
      dfs(j,i,lvl+1,max(gg,h));
    }
  }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

    for (int i=1;i<=n;i++) {
      if (v[i].size()>1) continue;
      cldis(i,0,0);
      dfs(i,0,0,0);
    }

    cout<<ans<<' '<<cnt/2;
}

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