#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "cowpatibility"
#define pll pair<ll, ll>
#define pii pair<pll, ll>
#define fi first
#define se second
using namespace std;
const ll mod = 998244353;
const ll N = 5e5+5;
const int base = 400;
ll n, m, t, k, T, ans, tong, lab[N], a[N], b[N], d[N], in[N], out[N], lazy[N*4];
ll st[N*4];
vector<ll> adj[N], kq, val[N];
string s[N], ss;
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n & 1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
void build(ll id, ll l, ll r)
{
if(l == r)
{
st[id] = a[l];
return;
}
ll mid = (l + r) / 2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = max(st[id*2], st[id*2+1]);
}
void down(ll id)
{
if(lazy[id] == 0)return;
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
st[id*2] += lazy[id];
st[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val)
{
if(u <= l && r <= v)
{
st[id] += val;
lazy[id] += val;
return;
}
if(u > r || l > v || u > v)return;
ll mid = (l + r) / 2;
down(id);
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
st[id] = max(st[id*2], st[id*2+1]);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v || u > v)return -mod;
ll mid = (l + r) / 2;
down(id);
return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
void dfs1(ll u, ll p)
{
in[u] = ++k;
for(ll v : adj[u])
{
if(v == p)continue;
b[v] = b[u] + 1;
dfs1(v, u);
}
if(adj[u].size() == 1)a[in[u]] = b[u];
else a[in[u]] = -mod;
out[u] = k;
}
void dfs2(ll u, ll p)
{
if(adj[u].size() == 1)return;
vector<ll> val;
val.pb(max(get(1, 1, n, 1, in[u]-1), get(1, 1, n, out[u]+1, n)));
for(ll v : adj[u])
{
if(v == p)continue;
val.pb(get(1, 1, n, in[v], out[v]));
}
sort(val.rbegin(), val.rend());
if(val.size() > 2)
{
if(val[0] * (val[1] + val[2]) > ans)
{
ans = val[0] * (val[1] + val[2]);
for(ll i = 2; i < val.size(); i ++)
{
if(val[i] == val[2])
{
if(val[0] == val[2])tong = i * (i + 1) / 2;
else if(val[1] == val[2])tong = i * (i - 1) / 2;
else tong = i - 1;
}
}
}
else if(val[0] * ( val[1] + val[2]) == ans)
{
for(ll i = 2; i < val.size(); i ++)
{
if(val[i] == val[2])
{
if(val[0] == val[2])k = i * (i - 1) * (i - 2) / 6;
else if(val[1] == val[2])k = i * (i - 1) / 2;
else k = i - 1;
}
}
tong += k;
}
}
for(ll v : adj[u])
{
if(v == p)continue;
update(1, 1, n, 1, n, 1);
update(1, 1, n, in[v], out[v], -2);
dfs2(v, u);
update(1, 1, n, 1, n, -1);
update(1, 1, n, in[v], out[v], 2);
}
}
void sol()
{
cin >> n;
for(int i = 1; i < n; i ++)
{
ll x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
tong = 1;
dfs1(1, 1);
build(1, 1, n);
dfs2(1, 1);
cout << ans << " "<<tong;
}
int main()
{
if(fopen(task".in", "r"))
{
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
/*
abba
4
bb
1
aa
10
ab
2
ba
5
*/
Compilation message
road.cpp: In function 'void dfs2(long long int, long long int)':
road.cpp:103:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(ll i = 2; i < val.size(); i ++)
| ~~^~~~~~~~~~~~
road.cpp:115:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(ll i = 2; i < val.size(); i ++)
| ~~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:158:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
158 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road.cpp:159:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
159 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
39472 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
39444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
39472 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
39444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
39472 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
39444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
