Submission #973888

#TimeUsernameProblemLanguageResultExecution timeMemory
973888PieArmyHard route (IZhO17_road)C++17
100 / 100
511 ms86356 KiB
#pragma GCC optimize("O3,fast-math,unroll-all-loops") 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(komsu[pos].size()>2){ 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]; } ll res=dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0]); if(res>ans){ ans=res; say=art; } else if(res==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...