/*
.:*+=%@@@@@@=-.
.:=@#@@@#@@#######%==*.
.-=####@######%*-.....:%##%.
.*@###########%+:--........-%@-
.*@##############@+--.........-:%-
.+##################@==%%%%=+*:----+.
.-@####################%++%@@@@@=+**%@@*
.%###################@%%@@@###@%+:--%@@%.
-@###################@%%%%*::*%++:-----=@+.
-#####################@%=++++++*:-------.-=:
.+####################@%++*::-:::--::*:::***=:
.@#####################%=++*::::-:::++*=##@@#@-
..#####################@%%=++**:::::**+%@#@%%##-..
.%####################@@%=+++*+****::*=@######@.
.=######################@%%==+==++**+=@%@##@###+:...
-#######################@@@%%%===++=@@@%=++===*::--...
-########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------
o###########oo
o##" ""##o
o#" "##
o#" "#o
#" ## ## "##
#" ##
# ################### #
# #
# #
# #
# #
# #
# #
#o #
"#o ##
"#o ##
"#o o#"
"#o ##
"#o o#"
"#ooo ooo#######oo
############### "######o
o###"" "###o # ###
o###o oooo ### oo####"
o###**# #**# ############"
""##""""""""""########### #
# oooooooo#"#** ## #
# # # # ** ## #
#o# #o# *****###ooo#
##
## o###o
## o##***##
o########## #***#**##o
o##" ""### #***##***#
o#######o ### oo#### ##**####*#
o##" ""#############"" ##****###
##" ## ##*##*###
## ### ##### ##
## ### # ## #
## ## #
## ##
## ###
## ###oo
### ""###
###
###
*/
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int mysqrt(ll x){
int l = 0, r = 1e9 + 1;
while (r - l > 1){
int m = (l + r) / 2;
if (m * (ll)m <= x)
l = m;
else
r = m;
}
return l;
}
mt19937 rnd(1337);
ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;
ll myrand(){
ll ZR = (XR * AR + YR * BR + CR) % MODR;
XR = YR;
YR = ZR;
return ZR;
}
const int Mod = 1e9 + 7;
int bpow(int x, int y){
if (y == 0)
return 1;
if (y == 1)
return x;
int ret = bpow(x, y >> 1);
ret = (ret * (ll)ret) % Mod;
if (y & 1)
ret = (ret * (ll)x) % Mod;
return ret;
}
int bdiv(int x, int y){
return (x * (ll)bpow(y, Mod - 2)) % Mod;
}
void setmin(int &x, int y){
x = min(x, y);
}
void setmax(int &x, int y){
x = max(x, y);
}
const ll llinf = 1e18 + 100;
const int maxn = 5e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;
int n;
vector<int> e[maxn];
vector<int> q[maxn];
vector<int> g[maxn];
ll ans, answer = 1;
void upd(ll x, ll y){
if (ans > x)
return;
if (ans < x)
ans = x, answer = 0;
answer += y;
}
int dfs0(int v, int par){
int ret = 0;
q[v].resize(e[v].size());
g[v].resize(e[v].size());
for (int i = 0; i < e[v].size(); i++)
if (e[v][i] != par){
q[v][i] = dfs0(e[v][i], v) + 1;
ret = max(ret, q[v][i]);
}
return ret;
}
void dfs(int v, int par, int pv){
int a = 0, b = 0, c = 0, x = 0, y = 0, z = 0;
if (pv)
a = pv, x = 1;
for (int i = 0; i < e[v].size(); i++)
if (e[v][i] != par){
if (a < q[v][i])
c = b, b = a, a = q[v][i], z = y, y = x, x = 1;
else
if (a == q[v][i])
x++;
else
if (b < q[v][i])
c = b, b = q[v][i], z = y, y = 1;
else
if (b == q[v][i])
y++;
else
if (c < q[v][i])
c = q[v][i], z = 1;
else
if (c == q[v][i])
z++;
}
if (x + y + z > 2){
if (x == 1)
if (y == 1)
upd(a * (ll)(b + c), z);
else
upd(a * (ll)2 * b, y * (ll)(y - 1) / 2);
else
if (x > 2)
upd(a * (ll)2 * a, x * (ll)(x - 1) / 2);
else
upd(a * (ll)(a + b), 2 * y);
}
g[v][0] = q[v][0];
for (int i = 1; i < q[v].size(); i++)
g[v][i] = max(q[v][i], g[v][i - 1]);
a = pv;
for (int i = q[v].size() - 1; i >= 0; i--)
if (e[v][i] != par){
dfs(e[v][i], v, max(a, (i ? g[v][i - 1] : 0)) + 1);
a = max(a, q[v][i]);
}
}
int dist, dans;
void getfar(int v, int par, int ds){
if (ds > dist)
dist = ds, dans = v;
for (auto i : e[v])
if (i != par)
getfar(i, v, ds + 1);
}
ll X, Y = 1;
bool vis[maxn];
int pt[maxn];
int getf(int v, int par){
int ret = 0;
for (auto i : e[v])
if (i != par)
ret = max(ret, getf(i, v) + 1);
return ret;
}
void go(int v, int par, int len){
pt[len] = v;
if (len && e[v].size() == 1){
for (int i = 0; i < n; i++)
vis[i] = 0;
for (int i = 0; i <= len; i++)
vis[pt[i]] = 1;
int z = 0;
for (int i = 0; i <= len; i++){
int u = pt[i];
for (auto j : e[u])
if (!vis[j])
z = max(z, getf(j, u) + 1);
}
if (X < z * len)
X = z * len, Y = 1;
else
if (X == z * len)
Y++;
return;
}
for (auto i : e[v])
if (i != par)
go(i, v, len + 1);
}
int main()
{
#ifdef ONPC
//ifstream cin("a.in");
//ofstream cout("a.out");
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#else
//ifstream cin("road.in");
//ofstream cout("road.out");
//freopen("money.in", "r", stdin);
//freopen("money.out", "w", stdout);
#endif // ONPC
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++){
int v, u;
cin >> v >> u;
v--;
u--;
e[v].push_back(u);
e[u].push_back(v);
}
dfs0(0, -1);
dfs(0, -1, 0);
for (int i = 0; i < n; i++)
if (e[i].size() == 1)
go(i, -1, 0);
Y /= 2;
assert(ans == X);
assert(Y >= answer);
cout << X << ' ' << Y;
//cout << ans << ' ' << answer;
}
Compilation message
road.cpp: In function 'int dfs0(int, int)':
road.cpp:177:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < e[v].size(); i++)
^
road.cpp: In function 'void dfs(int, int, int)':
road.cpp:189:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < e[v].size(); i++)
^
road.cpp:222:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < q[v].size(); i++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 3 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 5 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 6 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 7 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 8 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 9 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 10 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 11 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 12 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 13 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 15 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 16 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 17 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 18 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 19 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 20 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 21 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 22 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 23 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 24 |
Correct |
13 ms |
39788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 3 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 5 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 6 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 7 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 8 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 9 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 10 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 11 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 12 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 13 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 15 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 16 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 17 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 18 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 19 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 20 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 21 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 22 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 23 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 24 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 25 |
Execution timed out |
2000 ms |
40188 KB |
Execution timed out |
| 26 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 3 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 4 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 5 |
Correct |
3 ms |
39788 KB |
Output is correct |
| 6 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 7 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 8 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 9 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 10 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 11 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 12 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 13 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 14 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 15 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 16 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 17 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 18 |
Correct |
16 ms |
39788 KB |
Output is correct |
| 19 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 20 |
Correct |
9 ms |
39788 KB |
Output is correct |
| 21 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 22 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 23 |
Correct |
6 ms |
39788 KB |
Output is correct |
| 24 |
Correct |
13 ms |
39788 KB |
Output is correct |
| 25 |
Execution timed out |
2000 ms |
40188 KB |
Execution timed out |
| 26 |
Halted |
0 ms |
0 KB |
- |
