#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n;
vector<int> adj[N];
vector<ipair> D[N];
ipair dpD[N] , dpU[N];
int mx , cnt;
void dfsD(int u = 1 , int p = 0){
for(int v : adj[u]){
if(v==p)continue;
dfsD(v , u);
if(dpD[v].F + 1 > dpD[u].F) dpD[u] = dpD[v] , dpD[u].F++;
else if(dpD[v].F + 1 == dpD[u].F) dpD[u].S += dpD[v].S;
}
if(adj[u].size() == 1 && u != 1) dpD[u].S = 1;
for(int v : adj[u]) if(v != p)D[u].emplace_back(dpD[v].F + 1, dpD[v].S);
}
void dfsU(int u = 1, int p = 0){
pair<int , int > d1 , d2;
d1.F = d1.S = d2.F= d2.S = 0;
d1 = dpD[u];
///d1.F--;
//cout << d1.F << " " << d1.S << " kaaa " << endl;
for(int v : adj[u]){
if(v==p || d1.F == dpD[v].F + 1)continue;
if(d2.F < dpD[v].F + 1)d2 = dpD[v];
else if(d2.F == dpD[v].F + 1) d2.S += dpD[v].S;
}
//cout << d2.F << " " << d2.S << " uaaaa "<< endl;
if(u == 1) dpU[u].S = 1;
for(int v : adj[u]){
if(v==p)continue;
if(d1.F == dpD[v].F + 1 && d1.S == dpD[v].S) dpU[v] = d2;
else if(d1.F == dpD[v].F + 1 && d1.S > dpD[v].S) dpU[v].F = d1.F , dpU[v].S = d1.S - dpD[v].S;
else dpU[v] = d1;
if(dpU[v].F < dpU[u].F) dpU[v] = dpU[u];
else if(dpU[v].F == dpU[u].F) dpU[v].S += dpU[u].S;
dpU[v].F++;
dfsU(v , u);
}
}
void solve(){
//cout << "HOO" << endl;
for(int u = 1; u <= n; ++u){
if(D[u].size() < 3) continue;
sort(D[u].rbegin() , D[u].rend());
int x1 = D[u][0].F , x2 = D[u][1].F , x3 = D[u][2].F;
//cout << x1 << " " << x2 << " " << x3 << endl;
mx = max(mx , x1 * (x2 + x3));
}
//cout << mx << " mx "<<endl;
for(int u = 1; u <= n; ++u){
if(D[u].size() < 3)continue;
int x1 = D[u][0].F , x2 = D[u][1].F , x3 = D[u][2].F;
if(mx != x1 * (x2 + x3)) continue;
int WW = 1;
if(x1 == x3){
int A= 0;
for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)A++, WW *= D[u][x].S;
cnt += (WW * A * (A - 1) * (A - 2)) / 2;
continue;
}
if(x1 == x2){
int A =0;
for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
cnt += A * WW; continue;
}
if(x2 == x3){
int A= 0;
for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2)A++, WW *= D[u][x].S;
cnt += (WW * A * (A - 1)) / 2;continue;
}
int A = 0;
for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
cnt += A * WW;
}
}
main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1; i < n; ++i){
int u , v; cin >> u >> v;
adj[u].emplace_back(v); adj[v].emplace_back(u);
}
dfsD();
//for(int i = 1; i <= n; ++i)cout << dpD[i].F << " "; cout << endl;
dfsU();
for(int i = 1; i <= n; ++i)if(dpU[i].F)D[i].emplace_back(dpU[i]);
//for(int i= 1; i <= n; ++i)cout << dpU[i].F << " "; cout << endl;
solve();
if(!cnt)cnt = 1;
cout << mx << " " << cnt;
}
Compilation message
road.cpp: In function 'void solve()':
road.cpp:67:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F ==x1)A++, WW *= D[u][x].S;
| ~~^~~~~~~~~~~~~
road.cpp:73:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int x = 0; x < D[u].size(); ++x) if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
| ~~^~~~~~~~~~~~~
road.cpp:78:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int x = 0; x< D[u].size(); ++x)if(D[u][x].F == x2)A++, WW *= D[u][x].S;
| ~^~~~~~~~~~~~~
road.cpp:82:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int x = 0;x < D[u].size(); ++x)if(D[u][x].F == x3)A++ , WW *= D[u][x].S;
| ~~^~~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:87:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
87 | main (){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 5 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 7 |
Incorrect |
15 ms |
23788 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 5 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 7 |
Incorrect |
15 ms |
23788 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23788 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23788 KB |
Output is correct |
| 5 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 7 |
Incorrect |
15 ms |
23788 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
