제출 #1127203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127203		bekzhan29	Hard route (IZhO17_road)	C++20	52 / 100	480 ms	88084 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define INF (long long)(2e15)
#define mod2 998244353
#define mod 1000000007
#define eps 1e-9
#define abs(x) ((x)>=0?(x):-(x))
#define y1 solai
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<pll, ll> plll;
mt19937 rng(29);
const ll N=500100;
ll n,x,y,ans,cnt=1,d[N],c[N];
vector<ll>v[N];
bool cmp(pll a, pll b)
{
	return a.fi>b.fi;
}
void calc(vector<pll> &v)
{
	if(v.size()<3)
		return;
	sort(v.begin(),v.end(),&cmp);
	ll a=v[0].fi,b=v[1].fi,cc=v[2].fi;
	if(a==cc)
	{
		ll sum=0;
		for(ll i=0;i<v.size();i++)
		{
			if(v[i].fi!=a)
				break;
			if(ans==a*(b+cc))
			{
				cnt+=v[i].se*sum;
			}
			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].se*sum;
			}
			sum+=v[i].se;
		}
		return;
	}
	if(a>b&&b==cc)
	{
		ll sum=0;
		for(ll i=1;i<v.size();i++)
		{
			if(v[i].fi!=b)
				break;
			if(ans==a*(b+cc))
			{
				cnt+=v[i].se*sum;
			}
			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].se*sum;
			}
			sum+=v[i].se;
		}
		return;
	}
	if(a>b&&b>cc)
	{
		ll sum=v[1].se;
		for(ll i=2;i<v.size();i++)
		{
			if(v[i].fi!=cc)
				break;
			if(ans==a*(b+cc))
			{
				cnt+=v[i].se*sum;
			}
			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].se*sum;
			}
			sum+=v[i].se;
		}
		return;
	}
	ll sum=v[0].se+v[1].se;
	for(ll i=2;i<v.size();i++)
	{
		if(v[i].fi!=cc)
			break;
		if(ans==a*(b+cc))
		{
			cnt+=v[i].se*sum;
		}
		else if(ans<a*(b+cc))
		{
			ans=a*(b+cc);
			cnt=v[i].se*sum;
		}
		sum+=v[i].se;
	}
}
void dfs(ll x, ll pr=0)
{
	d[x]=1;
	c[x]=1;
	for(ll to:v[x])
	{
		if(to==pr)
			continue;
		dfs(to,x);
		if(d[to]+1>d[x])
		{
			d[x]=d[to]+1;
			c[x]=c[to];
		}
		else if(d[to]+1==d[x])
			c[x]+=c[to];
	}
}
void dfs2(ll x, ll pr=0, ll du=0, ll dc=0)
{
	vector<pll>cur;
	if(pr)
		cur.pb({du,dc});
	for(ll to:v[x])
	{
		if(to==pr)
			continue;
		cur.pb({d[to],c[to]});
	}
	calc(cur);
	if(!pr&&v[x].size()==1)
		dc=1;
	ll mx1=du,mx2=0,cnt1=dc,cnt2=0;
	for(ll to:v[x])
	{
		if(to==pr)
			continue;
		if(d[to]>mx1)
		{
			mx2=mx1;
			cnt2=cnt1;
			mx1=d[to];
			cnt1=c[to];
		}
		else if(d[to]==mx1)
		{
			cnt1+=c[to];
		}
		else if(d[to]>mx2)
		{
			mx2=d[to];
			cnt2=c[to];
		}
	}
	for(ll to:v[x])
	{
		if(to==pr)
			continue;
		if(d[to]<mx1)
			dfs2(to,x,mx1+1,cnt1);
		else if(cnt1==c[to])
			dfs2(to,x,mx2+1,cnt2);
		else
			dfs2(to,x,mx1+1,cnt1-c[to]);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin>>n;
	for(ll i=1;i<n;i++)
		cin>>x>>y,v[x].pb(y),v[y].pb(x);
	dfs(1);
	dfs2(1);
	cout<<ans<<" "<<cnt<<endl;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7

4
1 2
2 3
2 4

5
1 2
2 3
3 4
4 5

*/

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