제출 #1130764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130764		brover29	Hard route (IZhO17_road)	C++20	100 / 100	601 ms	136972 KiB

road

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=5e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,x,y,ans,cnt=1,d[N],c[N];
vector<ll>v[N];
bool cmp(pair<ll,ll> a, pair<ll,ll> b){
	return a.f>b.f;
}
void calc(vector<pair<ll,ll>> &v){
	if(v.size()<3)return;
	sort(v.begin(),v.end(),&cmp);
	ll a=v[0].f,b=v[1].f,cc=v[2].f;
	if(a==cc){
		ll sum=0;
		for(ll i=0;i<v.size();i++){
			if(v[i].f!=a)break;
			if(ans==a*(b+cc))cnt+=v[i].s*sum;

			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].s*sum;
			}
			sum+=v[i].s;
		}
		return;
	}
	if(a>b&&b==cc)
	{
		ll sum=0;
		for(ll i=1;i<v.size();i++)
		{
			if(v[i].f!=b)
				break;
			if(ans==a*(b+cc))
			{
				cnt+=v[i].s*sum;
			}
			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].s*sum;
			}
			sum+=v[i].s;
		}
		return;
	}
	if(a>b&&b>cc)
	{
		ll sum=v[1].s;
		for(ll i=2;i<v.size();i++)
		{
			if(v[i].f!=cc)
				break;
			if(ans==a*(b+cc))
			{
				cnt+=v[i].s*sum;
			}
			else if(ans<a*(b+cc))
			{
				ans=a*(b+cc);
				cnt=v[i].s*sum;
			}
		}
		return;
	}
	ll sum=v[0].s+v[1].s;
	for(ll i=2;i<v.size();i++)
	{
		if(v[i].f!=cc)
			break;
		if(ans==a*(b+cc))
		{
			cnt+=v[i].s*sum;
		}
		else if(ans<a*(b+cc))
		{
			ans=a*(b+cc);
			cnt=v[i].s*sum;
		}
	}
}
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<pair<ll,ll>>cur;
	if(pr)cur.push_back({du,dc});
	for(ll to:v[x]){
		if(to!=pr)cur.push_back({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++){
        ll vv,u;
        cin>>vv>>u;
        v[vv].push_back(u);
        v[u].push_back(vv);
	}
	dfs(1);
	dfs2(1);
	cout<<ans<<" "<<cnt;
}

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