제출 #973868

#제출 시각아이디문제언어결과실행 시간메모리
973868PieArmyHard route (IZhO17_road)C++17
100 / 100
574 ms94036 KiB
typedef long long ll;
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int n;
ll dp[500001][3][3],ans=0,say=1;
vector<int>komsu[500001];

void ekle(int loc,int x,ll cnt){
    if(x>dp[loc][0][0]){
        swap(dp[loc][1],dp[loc][2]);
        swap(dp[loc][0],dp[loc][1]);
        dp[loc][0][0]=x;
        dp[loc][0][1]=0;
        dp[loc][0][2]=0;
    }
    else if(x>dp[loc][1][0]){
        swap(dp[loc][1],dp[loc][2]);
        dp[loc][1][0]=x;
        dp[loc][1][1]=0;
        dp[loc][1][2]=0;
        if(x==dp[loc][0][0]){
            dp[loc][1][1]=dp[loc][0][1];
            dp[loc][1][2]=dp[loc][0][2];
        }
    }
    else if(x>dp[loc][2][0]){
        dp[loc][2][0]=x;
        dp[loc][2][1]=0;
        dp[loc][2][2]=0;
        if(x==dp[loc][1][0]){
            dp[loc][2][1]=dp[loc][1][1];
            dp[loc][2][2]=dp[loc][1][2];
        }
    }
    for(int i=0;i<3;i++){
        if(x==dp[loc][i][0]){
            dp[loc][i][2]+=dp[loc][i][1]*cnt;
            dp[loc][i][1]+=cnt;
        }
    }
}

void dfs1(int pos,int root){
    dp[pos][0][1]=1;
    for(int x:komsu[pos]){
        if(x==root)continue;
        dfs1(x,pos);
        ekle(pos,dp[x][0][0]+1,dp[x][0][1]);
    }
}

void dfs2(int pos,int root){
    if(root){
        if(dp[root][0][0]-1==dp[pos][0][0]){
            ll y=dp[root][1][1];
            if(dp[root][1][0]-1==dp[pos][0][0]){
                y-=dp[pos][0][1];
            }
            ekle(pos,dp[root][1][0]+1,y);
        }
        else{
            ekle(pos,dp[root][0][0]+1,dp[root][0][1]);
        }
    }
    if(dp[pos][0][0]&&dp[pos][1][0]&&dp[pos][2][0]){
        ll art=0;
        if(dp[pos][1][0]==dp[pos][2][0]){
            art=dp[pos][1][2];
        }
        else{
            art=dp[pos][1][1]*dp[pos][2][1];
        }
        if(dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0])>ans){
            ans=dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0]);
            say=art;
        }
        else if(dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0])==ans){
            say+=art;
        }
    }
    for(int x:komsu[pos]){
        if(x==root)continue;
        dfs2(x,pos);
    }
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        komsu[a].pb(b);
        komsu[b].pb(a);
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans<<" "<<say;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...