Submission #1185145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185145		ziyad_alharbi	Hard route (IZhO17_road)	C++20	0 / 100	5 ms	12104 KiB

road

#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++;
        array<int,2>c[]={(*y),(*j),(*k)};
        sort(c,c+3);
        int b[]={c[0][1],c[1][1],c[2][1]},a[]={c[0][0],c[1][0],c[2][0]};
        int l=a[0]+a[1],r=a[2];
        // cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
        bool bl=a[0]==a[1]&&a[1]==a[2];
        // cout<<bl<<' ';
        // cout<<b[0]<<' '<<b[1]<<' '<<b[2]<<'\n';
        if(l*r>ans[0])
        {
            ans={l*r,b[0]*b[1]*(bl?3*a[2]:1)};
            k++;
            int sum=b[0]+b[1]+b[2];
            while(k!=st.rend())
            {
                int lf=(*k)[0],rh=(*k)[1];
                if(lf!=a[0])break;
                if(!bl)ans[1]+=b[1]*rh;
                else
                {
                    ans[1]+=rh*sum;
                    sum+=rh;
                }
                k++;
            }
        }
        else 
        {
            ans[1]+=b[0]*b[1]*(bl?3*a[2]:1);
            k++;
            int sum=b[0]+b[1]+b[2];
            while(k!=st.rend())
            {
                int lf=(*k)[0],rh=(*k)[1];
                if(lf!=a[0])break;
                if(!bl)ans[1]+=b[1]*rh;
                else
                {
                    ans[1]+=rh*sum;
                    sum+=rh;
                }
                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;
}

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