#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 500015
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];
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 (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;
map<int,int>have,son;
for (auto i:g[p]){
have[dp[i].x+1]+=dp[i].y;
son[dp[i].x+1]++;
}
for (auto i:g[p]){
auto [d,c]=dp[i]; d++;
pii tmp=dp[p];
have[d]-=c; son[d]--;
auto it=prev(have.end());
while (it!=have.begin()&&(it->y)==0) it=prev(it);
if (have.count(a-d)&&have[a-d]){
son[a-d]--;
if (son.count(b)&&son[b])
cnt=(cnt+(long long)c*have[a-d]);
son[a-d]++;
}
if (have.count(b-d)&&have[b-d]){
son[b-d]--;
if (son.count(a)&&son[a])
cnt=(cnt+(long long)c*have[b-d]);
son[b-d]++;
}
dp[p]=*it;
if (i!=lp)
dfs2(i,p);
dp[p]=tmp;
have[d]+=c; son[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';
}
Compilation message
road.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
| ^
road.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
road.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
road.cpp:20:22: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
20 | void dfs(int p,int lp){
| ^
road.cpp:20:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:20:22: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
35 | void dfs1(int p,int lp,pii val){
| ^
road.cpp:35:31: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:35:31: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
57 | void relax(int x,int y){
| ^
road.cpp:57:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:57:23: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
64 | void solve(){
| ^
road.cpp:64:12: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:64:12: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
81 | void dfs2(int p,int lp){
| ^
road.cpp:81:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:81:23: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
113 | signed main(){
| ^
road.cpp:113:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
road.cpp:113:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 9 |
Correct |
7 ms |
12108 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 13 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 16 |
Correct |
9 ms |
12108 KB |
Output is correct |
| 17 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 18 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 22 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 23 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 9 |
Correct |
7 ms |
12108 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 13 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 16 |
Correct |
9 ms |
12108 KB |
Output is correct |
| 17 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 18 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 22 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 23 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 25 |
Correct |
10 ms |
12964 KB |
Output is correct |
| 26 |
Correct |
11 ms |
13268 KB |
Output is correct |
| 27 |
Correct |
11 ms |
12884 KB |
Output is correct |
| 28 |
Correct |
12 ms |
13396 KB |
Output is correct |
| 29 |
Correct |
11 ms |
13268 KB |
Output is correct |
| 30 |
Correct |
12 ms |
13536 KB |
Output is correct |
| 31 |
Correct |
10 ms |
13524 KB |
Output is correct |
| 32 |
Correct |
10 ms |
13108 KB |
Output is correct |
| 33 |
Correct |
10 ms |
13224 KB |
Output is correct |
| 34 |
Correct |
11 ms |
13524 KB |
Output is correct |
| 35 |
Correct |
10 ms |
13400 KB |
Output is correct |
| 36 |
Correct |
10 ms |
13268 KB |
Output is correct |
| 37 |
Correct |
11 ms |
13584 KB |
Output is correct |
| 38 |
Correct |
12 ms |
14548 KB |
Output is correct |
| 39 |
Correct |
11 ms |
13012 KB |
Output is correct |
| 40 |
Correct |
12 ms |
12628 KB |
Output is correct |
| 41 |
Correct |
12 ms |
12532 KB |
Output is correct |
| 42 |
Correct |
12 ms |
12316 KB |
Output is correct |
| 43 |
Correct |
9 ms |
12320 KB |
Output is correct |
| 44 |
Correct |
10 ms |
12356 KB |
Output is correct |
| 45 |
Correct |
10 ms |
12244 KB |
Output is correct |
| 46 |
Correct |
9 ms |
12244 KB |
Output is correct |
| 47 |
Correct |
10 ms |
12368 KB |
Output is correct |
| 48 |
Correct |
9 ms |
12372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 4 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 7 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 9 |
Correct |
7 ms |
12108 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 12 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 13 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 16 |
Correct |
9 ms |
12108 KB |
Output is correct |
| 17 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 18 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 19 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 20 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 21 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 22 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 23 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 24 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 25 |
Correct |
10 ms |
12964 KB |
Output is correct |
| 26 |
Correct |
11 ms |
13268 KB |
Output is correct |
| 27 |
Correct |
11 ms |
12884 KB |
Output is correct |
| 28 |
Correct |
12 ms |
13396 KB |
Output is correct |
| 29 |
Correct |
11 ms |
13268 KB |
Output is correct |
| 30 |
Correct |
12 ms |
13536 KB |
Output is correct |
| 31 |
Correct |
10 ms |
13524 KB |
Output is correct |
| 32 |
Correct |
10 ms |
13108 KB |
Output is correct |
| 33 |
Correct |
10 ms |
13224 KB |
Output is correct |
| 34 |
Correct |
11 ms |
13524 KB |
Output is correct |
| 35 |
Correct |
10 ms |
13400 KB |
Output is correct |
| 36 |
Correct |
10 ms |
13268 KB |
Output is correct |
| 37 |
Correct |
11 ms |
13584 KB |
Output is correct |
| 38 |
Correct |
12 ms |
14548 KB |
Output is correct |
| 39 |
Correct |
11 ms |
13012 KB |
Output is correct |
| 40 |
Correct |
12 ms |
12628 KB |
Output is correct |
| 41 |
Correct |
12 ms |
12532 KB |
Output is correct |
| 42 |
Correct |
12 ms |
12316 KB |
Output is correct |
| 43 |
Correct |
9 ms |
12320 KB |
Output is correct |
| 44 |
Correct |
10 ms |
12356 KB |
Output is correct |
| 45 |
Correct |
10 ms |
12244 KB |
Output is correct |
| 46 |
Correct |
9 ms |
12244 KB |
Output is correct |
| 47 |
Correct |
10 ms |
12368 KB |
Output is correct |
| 48 |
Correct |
9 ms |
12372 KB |
Output is correct |
| 49 |
Correct |
774 ms |
121904 KB |
Output is correct |
| 50 |
Correct |
742 ms |
137728 KB |
Output is correct |
| 51 |
Correct |
764 ms |
151192 KB |
Output is correct |
| 52 |
Correct |
754 ms |
103116 KB |
Output is correct |
| 53 |
Incorrect |
648 ms |
173516 KB |
Output isn't correct |
| 54 |
Halted |
0 ms |
0 KB |
- |
