Submission #1130728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130728		brover29	Hard route (IZhO17_road)	C++20	52 / 100	2097 ms	52836 KiB

road

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=5e5+29;
ll n,ans,cnt=1,d[N],c[N];
vector<ll>g[N];
void dfs(ll v,ll pr=0){
	d[v]=1;
	c[v]=1;
	for(ll to:g[v]){
		if(to==pr)continue;
		dfs(to,v);
		if(d[to]+1==d[v])c[v]+=c[to];
		if(d[to]+1>d[v]){
			d[v]=d[to]+1;
			c[v]=c[to];
		}
	}
}
bool cmp(ll a, ll b){
	return d[a]>d[b];
}
void solve(ll x){
	dfs(x);
	sort(g[x].begin(),g[x].end(),&cmp);
	for(ll j=0;j<g[x].size();j++){
		for(ll k=j+1;k<g[x].size();k++){
			for(ll i=0;i<g[x].size();i++){
				if(i==j||i==k)continue;
				ll a=g[x][i],b=g[x][j],cc=g[x][k];
				if(d[a]*(d[b]+d[cc])==ans){
					cnt+=c[b]*c[cc];
					break;
				}
				if(d[a]*(d[b]+d[cc])>ans){
					ans=d[a]*(d[b]+d[cc]);
					cnt=c[b]*c[cc];
					break;
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n;
	for(ll i=1;i<n;i++){
        ll v,u;
        cin>>v>>u;
        g[v].push_back(u);
        g[u].push_back(v);
	}
	for(ll i=1;i<=n;i++){
		if(g[i].size()>=3){
			solve(i);
		}
	}
	cout<<ans<<" "<<cnt<<'\n';
}

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