Submission #827798

#TimeUsernameProblemLanguageResultExecution timeMemory
827798EthanKim8683Hard route (IZhO17_road)C++17
0 / 100
7 ms12084 KiB
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=500000;
vector<I>adjs[N];
I dp1[N],dp2[N];
vector<I>curs;
I cnts[N];
pair<Lli,Lli>res={0,1};
void dfs1(I a,I p=-1){
  for(auto b:adjs[a])if(b!=p){
    dfs1(b,a);
    dp1[a]=max(dp1[a],dp1[b]+1);
  }
}
void dfs2(I a,I p=-1){
  I low=dp2[a];
  for(auto b:adjs[a])if(b!=p){
    dp2[b]=max(dp2[b],low+1);
    low=max(low,dp1[b]+1);
  }
  reverse(adjs[a].begin(),adjs[a].end());
  low=dp2[a];
  for(auto b:adjs[a])if(b!=p){
    dp2[b]=max(dp2[b],low+1);
    low=max(low,dp1[b]+1);
  }
  curs.clear(),curs.push_back(dp2[a]);
  for(auto b:adjs[a])if(b!=p)curs.push_back(dp1[b]+1);
  if(curs.size()>=3){
    sort(curs.rbegin(),curs.rend());
    Lli x=curs[0],y=curs[1],z=curs[2];
    for(auto i:curs)cnts[i]++;
    Lli val=x*(y+z),cnt=1;
    cnt*=cnts[x];
    cnt*=cnts[y]-(y==x);
    cnt*=cnts[z]-(z==x)-(z==y);
    if(y==z)cnt/=2;
    if(val>res.first)res={val,0};
    if(val==res.first)res.second+=cnt;
    for(auto i:curs)cnts[i]--;
  }
  for(auto b:adjs[a])if(b!=p)dfs2(b,a);
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n;cin>>n;
  for(I i=0;i<n-1;i++){
    I u,v;cin>>u>>v,u--,v--;
    adjs[u].push_back(v);
    adjs[v].push_back(u);
  }
  dfs1(0),dfs2(0);
  auto[val,cnt]=res;
  printf("%lli %lli\n",val,cnt);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...