#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <math.h>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <string.h>
#include <cstring>
#include <queue>
#include <iomanip>
#include <istream>
#include <map>
#include <list>
#include <stack>
#include <numeric>
#include <ostream>
#include <set>
#include <cassert>
#include <sstream>
#include <string>
#include <utility>
#include <stdio.h>
#include <vector>
using namespace std;
#define dout if (debug) cout
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;
#define REP(i,a,n) for (int i=a;i<n;i++)
#define db(x) cerr << #x << " = " << x << endl
#define PER(i,a,n) for (int i=n-1;i>=a;i--)
const int INF = 1000000404;
const ll MOD = 1000000007ll;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
template <typename t1, typename t2> inline void upmax(t1 &a, t2 b) { a = max(a, (t1)b); }
template <typename t1, typename t2> inline void upmin(t1 &a, t2 b) { a = min(a, (t1)b); }
template <typename T>inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T>inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T>inline T sqr(T a) { return a*a; }
template <typename T>inline bool pal(T &x)
{
int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; }return 1;
}
template <typename T>inline void rev(T &x) { int n = SZ(x); REP(i, 0, n / 2) swap(x[i], x[n - i - 1]); }
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
inline ll mp(ll a, ll b) { return (a << 31) + b; }
class compare{
public:
bool operator()(const int a, const int b) const {
return 1;
}
};
int SQ = 400;
#define debug 1
#define N 511111
VI g[N];
int d[N];
bool used[N];
int n;
void DFS(int v) {
used[v] = true;
for (auto x : g[v]) {
if (!used[x]) {
d[x] = d[v] + 1;
DFS(x);
}
}
}
int depth(int v, int p = -1, int h = 1) {
int ret = h;
for (auto x : g[v]){
if (x != p) upmax(ret, depth(x, v, h + 1));
}
return ret;
}
int crossed_depth(int v,int need, int p = -1, int h = 1) {
if (h == need) return 1;
int cnt = 0;
for (auto x : g[v]){
if (x != p) cnt += crossed_depth(x, need, v, h + 1);
}
return cnt;
}
void solve()
{
cin >> n;
REP(i, 1, n) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
// diameter
fill(used, used + N, false);
d[1] = 0;
DFS(1);
int x = 1;
REP(i, 1, n + 1) if (d[i] > d[x]) x = i;
fill(used, used + N, false);
d[x] = 0;
DFS(x);
int y = 1;
REP(i, 1, n + 1) if (d[i] > d[y]) y = i;
VI path;
int v = y;
while (x != v) {
path.push_back(v);
for (auto from : g[v]) {
if (d[from] < d[v]) {
v = from;
break;
}
}
}
path.push_back(x);
db(x); db(y);
// cout << "PATH: "; for (auto x : path) cout << x << ' '; cout << endl;
ll maxans= 0;
ll cntans = 0;
ll a, b, c;
REP(i, 1, SZ(path) - 1) {
a = i;
b = SZ(path) - a - 1;
int v = path[i];
int prv = path[i - 1];
int nxt = path[i + 1];
ll maxx = 0;
ll cnt = 0;
for (auto to : g[v]) {
if (to == prv || to == nxt) continue;
int h = depth(to, v);
upmax(maxx, h);
}
c = maxx;
upmax(maxans, (a + b)*c);
if (c != 0) upmax(maxans, max((a + c)*b, (b + c)*a));
}
db(maxans);
int plusone = 0;
REP(i, 1, SZ(path) - 1) {
a = i;
b = SZ(path) - a - 1;
int v = path[i];
int prv = path[i - 1];
int nxt = path[i + 1];
ll maxx = 0;
ll cnt = 0;
ll cd = 0;
for (auto to : g[v]) {
if (to == prv || to == nxt) continue;
int h = depth(to, v);
if (h > maxx) {
maxx = h;
cnt = 1;
}
else {
if (maxx == h) cnt++;
}
}
for (auto to : g[v]) {
if (to == prv || to == nxt) continue;
cd += crossed_depth(to, maxx, v);
}
c = maxx;
//db(c); db(cnt); db(cd);
if ((a + b)*c == maxans) plusone = 1;
if (c != 0 && (b + c)*a == maxans) {
if (c < b) cntans += cd; else {
cntans += (cnt*(cnt + 1)) / 2;
}
}
if (c != 0 && (a + c)*b == maxans) {
if (c < a) cntans += cd; else {
cntans += (cnt*(cnt + 1)) / 2;
}
}
}
cout << maxans << ' ' << max(1ll,cntans+plusone);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
//cin>>t;
while (t--) {
solve();
};
getchar();
getchar();
return 0;
}
Compilation message
road.cpp: In function 'void solve()':
road.cpp:149:6: warning: unused variable 'cnt' [-Wunused-variable]
ll cnt = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 5 |
Correct |
9 ms |
16648 KB |
Output is correct |
| 6 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
16648 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 5 |
Correct |
9 ms |
16648 KB |
Output is correct |
| 6 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
16648 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16648 KB |
Output is correct |
| 3 |
Correct |
6 ms |
16648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 5 |
Correct |
9 ms |
16648 KB |
Output is correct |
| 6 |
Correct |
0 ms |
16648 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
16648 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
