This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 500005;
int n;
vector<int> edge[MXN];
pii d[MXN], u[MXN];
int pnt[MXN];
pii operator+(pii a, pii b) {
if (a < b) swap(a, b);
if (a.fs == b.fs) a.sc += b.sc;
return a;
}
int SUM(vector<int> &v) {
int ans = 0;
for (auto &i : v) ans += i;
return ans;
}
struct P {
pii a, b;
void init() {
a = mp(0LL, 0LL);
b = mp(0LL, 0LL);
}
void PUSH(pii x) {
if (x.fs > a.fs) {
b = a;
a = x;
} else if (x.fs == a.fs) {
a.sc += x.sc;
} else if (x.fs > b.fs) {
b = x;
} else if (x.fs == b.fs) {
b.sc += x.sc;
}
}
pii GET(pii x) {
if (x.fs != a.fs) return a;
if (x.sc == a.sc) return b;
return mp(a.fs, a.sc - x.sc);
}
} p[MXN];
bool chain() {
int big = 0;
FOR(i, 1, n + 1) big = max(big, (int) edge[i].size());
return big <= 2;
}
void DFS1(int id, int par) {
pnt[id] = par;
d[id] = mp(0LL, 1LL);
for (auto &i : edge[id]) {
if (i == par) continue;
DFS1(i, id);
d[id] = d[id] + mp(d[i].fs + 1, d[i].sc);
}
}
void DFS2(int id, int par) {
u[id] = p[par].GET(mp(d[id].fs + 1, d[id].sc));
u[id].fs++;
p[id].init();
p[id].PUSH(u[id]);
for (auto &i : edge[id]) {
if (i == par) continue;
p[id].PUSH(mp(d[i].fs + 1, d[i].sc));
}
for (auto &i : edge[id]) {
if (i == par) continue;
DFS2(i, id);
}
}
pii calc(int id) {
if (edge[id].size() < 3) return mp(0LL, 0LL);
vector<int> c(3, -1);
vector<vector<int>> v(3);
c[0] = u[id].fs;
v[0].push_back(u[id].sc);
for (auto &i : edge[id]) {
if (i == pnt[id]) continue;
debug(d[i].fs + 1, d[i].sc);
bool f = false;
FOR(j, 0, 3) if (d[i].fs + 1 == c[j]) {
v[j].push_back(d[i].sc);
f = true;
break;
}
if (f) continue;
FOR(j, 0, 3) if (d[i].fs + 1 > c[j]) {
c.insert(c.begin() + j, d[i].fs + 1);
v.insert(v.begin() + j, vector<int>(1, d[i].sc));
break;
}
if (c.size() == 4) {
c.pop_back();
v.pop_back();
}
}
if (v[0].size() >= 3) {
int x = 2 * c[0] * c[0];
int s = SUM(v[0]), y = 0;
for (auto &i : v[0]) y += i * (s - i);
return mp(x, y / 2);
}
if (v[0].size() == 2) {
int x = c[0] * (c[0] + c[1]);
return mp(x, (v[0][0] + v[0][1]) * SUM(v[1]));
}
if (v[1].size() >= 2) {
int x = 2 * c[0] * c[1];
int s = SUM(v[1]), y = 0;
for (auto &i : v[1]) y += i * (s - i);
return mp(x, y / 2);
}
return mp(c[0] * (c[1] + c[2]), v[1][0] * SUM(v[2]));
}
void miku() {
int x, y;
cin >> n;
FOR(i, 1, n) {
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
if (chain()) {
cout << "0 1" << '\n';
return;
}
int rt = [&]() -> int {
FOR(i, 1, n + 1) if (edge[i].size() == 1) return i;
return 0;
}();
DFS1(rt, 0);
p[rt].init();
p[rt].PUSH(mp(0LL, 1LL));
for (auto &i : edge[rt]) p[rt].PUSH(mp(d[i].fs + 1, d[i].sc));
for (auto &i : edge[rt]) DFS2(i, rt);
debug(rt);
FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc);
pii ans = mp(0LL, 0LL);
FOR(i, 1, n + 1) {
// ans = ans + calc(i);
pii x = calc(i);
debug(i, x.fs, x.sc);
ans = ans + x;
}
cout << ans.fs << ' ' << ans.sc << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message (stderr)
road.cpp: In function 'pii calc(long long int)':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
road.cpp:103:9: note: in expansion of macro 'debug'
103 | debug(d[i].fs + 1, d[i].sc);
| ^~~~~
road.cpp: In function 'void miku()':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
road.cpp:161:5: note: in expansion of macro 'debug'
161 | debug(rt);
| ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
road.cpp:162:22: note: in expansion of macro 'debug'
162 | FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc);
| ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
road.cpp:167:9: note: in expansion of macro 'debug'
167 | debug(i, x.fs, x.sc);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |