제출 #740564

#제출 시각아이디문제언어결과실행 시간메모리
740564victor_gaoHard route (IZhO17_road)C++17
0 / 100
34 ms59060 KiB
#pragma GCC optimize("Ofast,unroll-loops,O3") //#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native") #include<bits/stdc++.h> //#include<bits/extc++.h> //#pragma pack(1) #define fast ios::sync_with_stdio(0); cin.tie(0); #define pii pair<int,int> #define x first #define y second #define N 500005 using namespace std; //using namespace __gnu_pbds; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset; //typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set; int n,fa[N]; long long ans=-1,cnt=0,a=0,b=0; pii dp[N],dp1[N]; vector<int>g[N]; map<int,int>have[N],son[N]; void dfs(int p,int lp){ fa[p]=lp; dp[p]={0,0}; if (g[p].size()==1){ dp[p].y=1; return; } for (auto i:g[p]){ if (i!=lp){ dfs(i,p); if (dp[p].x==dp[i].x+1) dp[p].y+=dp[i].y; else dp[p]=max(dp[p],pii(dp[i].x+1,dp[i].y)); } } } void dfs1(int p,int lp,pii val){ dp1[p]={val.x+1,val.y}; pii mx1=val,mx2={-1,0}; for (auto i:g[p]){ if (i!=lp){ if (mx1.x==dp[i].x) mx1.y+=dp[i].y; else if (mx2.x==dp[i].x) mx2.y+=dp[i].y; else mx2=max(mx2,dp[i]); if (mx1<mx2) swap(mx1,mx2); } } mx1.x++; mx2.x++; for (auto i:g[p]){ if (i!=lp){ if (dp[i].x==mx1.x-1&&dp[i].y==mx1.y) dfs1(i,p,mx2); else if (dp[i].x==mx1.x-1) dfs1(i,p,{mx1.x,mx1.y-dp[i].y}); else dfs1(i,p,mx1); } } } void relax(int x,int y){ swap(x,y); if ((long long)x*y>ans){ ans=x*y; a=x; b=y; } } void solve(){ for (int j=1;j<=n;j++){ vector<int>dep; for (auto i:g[j]){ if (i!=fa[j]) dep.push_back(dp[i].x+1); } if (dp1[j].y) dep.push_back(dp1[j].x); sort(dep.begin(),dep.end()); if (dep.size()>2){ int b1=dep.back(),b2=dep[dep.size()-2],b3=dep[dep.size()-3]; for (int i=0;i<(int)(dep.size())-2;i++) relax(dep[i],(b2+b1)); relax(b2,(b1+b3)); relax(b1,(b2+b3)); } } } void dfs2(int p,int lp){ //if (g[p].size()==1) return; for (auto i:g[p]){ have[p][dp[i].x+1]+=dp[i].y; son[p][dp[i].x+1]++; } for (auto i:g[p]){ auto [d,c]=dp[i]; d++; pii tmp=dp[p]; have[p][d]-=c; son[p][d]--; int have_find=0; if (have[p].count(a-d)&&have[p][a-d]){ son[p][a-d]--; if (son[p].count(b)&&son[p][b]) cnt=(cnt+(long long)c*have[p][a-d]),have_find=1; son[p][a-d]++; } if (have[p].count(b-d)&&have[p][b-d]){ son[p][b-d]--; if (son[p].count(a)&&son[p][a]) cnt=(cnt+(long long)c*have[p][b-d]),have_find=1; son[p][b-d]++; } if (!have_find){ if (have[p].count(dp1[i].x)) dp[p]={dp1[i].x-1,have[p][dp1[i].x-1]}; else dp[p]={dp1[i].x-1,0}; } if (i!=lp) dfs2(i,p); dp[p]=tmp; have[p][d]+=c; son[p][d]++; } } signed main(){ fast cin>>n; for (int i=1;i<n;i++){ int a,b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } int root=0; for (int i=1;i<=n;i++){ if (g[i].size()>1){ root=i; break; } } dfs(root,0); dfs1(root,0,pii(-1,0)); solve(); dfs2(root,0); if (a==b) cnt/=2; if (ans<=0) cout<<0<<' '<<1<<'\n'; else cout<<ans<<' '<<cnt/2<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...