Submission #827804

#	Time	Username	Problem	Language	Result	Execution time	Memory
827804		EthanKim8683	Hard route (IZhO17_road)	C++17	0 / 100	6 ms	12020 KiB

road

#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],val=x*(y+z);
    for(auto i:curs)cnts[i]++;
    if(val>res.first)res={val,0};
    if(val==res.first)res.second+=y==z?cnts[y]*(cnts[z]-1)/2:cnts[y]*cnts[z];
    for(auto i:curs)cnts[i]=0;
  }
  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);
}

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