#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n;
vector<int> adj[N], D[N];
int d[N], d1[N] , d2[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);
d[u] = max(d[u] , d[v] + 1);
if(d2[u] < d[v] + 1) d2[u] = d[v] + 1;
if(d2[u] > d1[u]) swap(d1[u] , d2[u]);
}
for(int v : adj[u]) if(v != p)D[u].emplace_back(d[v]+1);
}
void dfsU(int u = 1, int p = 0){
for(int v : adj[u]){
if(v==p)continue;
dpU[v] = dpU[u] + 1;
if(d[v] + 1 == d1[u]){
if(d2[u] != -1) dpU[v] = max(dpU[v], d2[u] + 1);
} else dpU[v] = max(dpU[v] , d1[u] + 1);
dfsU(v , u);
}
}
void solve(){
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] , x2 = D[u][1] , x3 = D[u][2];
// 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] , x2 = D[u][1] , x3 = D[u][2];
if(mx != x1 * (x2 + x3)) continue;
if(x1 == x2 && x2 == x3){
int x = 0;
for(x = 0; x < D[u].size(); ++x) if(D[u][x] != x1)break;
cnt += (x * (x - 1)) / 2; continue;
}
if(x1 == x2){
int A =0;
for(int x = 0; x < D[u].size(); ++x) if(D[u][x] == x3)A++;
cnt += A; continue;
}
if(x2 == x3){
int A= 0;
for(int x = 0; x< D[u].size(); ++x)if(D[u][x] == x2)A++;
cnt += (A * (A - 1)) / 2;continue;
}
int A = 0;
for(int x = 0;x < D[u].size(); ++x)if(D[u][x] == x3)A++;
cnt += A;
}
}
int 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);
}
memset(d1, -1 , sizeof(d1)); memset(d2 , -1, sizeof(d2));
dfsD();
//for(int i = 1; i <= n; ++i)cout << d1[i] << " " << d2[i] << endl;
/*
for(int i = 1; i <= n; ++i){
cout << i << ":: i ";
for(int x : D[i])cout << x << " ";cout << endl;
}
*/
dfsU();
for(int i = 1; i <= n; ++i)if(dpU[i])D[i].emplace_back(dpU[i]);
solve();
if(!cnt)cnt = 1;
cout << mx << " " << cnt;
//cout << endl;
//for(int i = 1; i <= n; ++i)cout << dpU[i] << " ";
}
Compilation message
road.cpp: In function 'void solve()':
road.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(x = 0; x < D[u].size(); ++x) if(D[u][x] != x1)break;
| ~~^~~~~~~~~~~~~
road.cpp:50:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int x = 0; x < D[u].size(); ++x) if(D[u][x] == x3)A++;
| ~~^~~~~~~~~~~~~
road.cpp:55:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int x = 0; x< D[u].size(); ++x)if(D[u][x] == x2)A++;
| ~^~~~~~~~~~~~~
road.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int x = 0;x < D[u].size(); ++x)if(D[u][x] == x3)A++;
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 2 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 3 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 4 |
Correct |
18 ms |
27756 KB |
Output is correct |
| 5 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 6 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 7 |
Incorrect |
17 ms |
27756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 2 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 3 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 4 |
Correct |
18 ms |
27756 KB |
Output is correct |
| 5 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 6 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 7 |
Incorrect |
17 ms |
27756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 2 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 3 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 4 |
Correct |
18 ms |
27756 KB |
Output is correct |
| 5 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 6 |
Correct |
17 ms |
27756 KB |
Output is correct |
| 7 |
Incorrect |
17 ms |
27756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
