Submission #1185138

#TimeUsernameProblemLanguageResultExecution timeMemory
1185138ziyad_alharbiHard route (IZhO17_road)C++20
0 / 100
5 ms12096 KiB
#include<bits/stdc++.h> using namespace std; #define int long long vector<int>v[500005]; int n; array<int,2>ans,ds[500005]; void d(int x,int p) { int mx=0,vl=1; for(auto i:v[x]) { if(i==p)continue; d(i,x); if(ds[i][0]>mx) { mx=ds[i][0]; vl=1; } else if(ds[i][0]==mx)vl+=ds[i][1]; } ds[x]={mx+1,vl}; } void f(int x,int p,array<int,2>vl) { multiset<array<int,2>>st; map<int,int>mp; if(x!=1) { st.insert(vl); mp[vl[0]]=0; } for(auto i:v[x]) { if(i==p)continue; st.insert(ds[i]); mp[ds[i][0]]=0; } if(st.size()>=3) { // cout<<x<<' '; auto y=st.rbegin(),j=st.rbegin(),k=st.rbegin(); j++; k++; k++; int a[]={(*y)[0],(*j)[0],(*k)[0]},b[]={(*y)[1],(*j)[1],(*k)[1]}; sort(a,a+3); int l=a[0]+a[1],r=a[2]; // cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n'; // cout<<b[0]<<' '<<b[1]<<' '<<b[2]<<'\n'; bool bl=a[0]==a[1]&&a[1]==a[2]; if(l*r>ans[0]) { ans={l*r,b[0]*b[1]*b[2]*(bl?3:1)}; k++; while(k!=st.rend()) { int lf=(*k)[0],rh=(*k)[1]; if(lf!=a[0])break; ans[1]+=b[1]*b[2]*rh*(bl?3:1); k++; } } else { ans[1]+=b[0]*b[1]*b[2]*(bl?3:1); k++; while(k!=st.rend()) { int lf=(*k)[0],rh=(*k)[1]; if(lf!=a[0])break; ans[1]+=b[1]*b[2]*rh*(bl?3:1); k++; } } } if(x==1) { st.insert(vl); mp[vl[0]]=0; } array<int,2>pr; int mx=0,mx2=0; for(auto [i,j]:st) { if(i>mx) { mx2=mx; mx=i; } else if(i>mx2)mx2=i; mp[i]+=j; } for(auto i:v[x]) { if(i==p)continue; mp[ds[i][0]]-=ds[i][1]; if(mp[mx]==0)pr={mx2,mp[mx2]}; else pr={mx,mp[mx]}; pr[0]++; f(i,x,pr); mp[ds[i][0]]+=ds[i][1]; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int x=0;x<n-1;x++) { int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } ans={0,1}; d(1,1); f(1,1,{0,1}); cout<<ans[0]<<' '<<ans[1]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...