| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 175671 | emil_physmath | Shymbulak (IZhO14_shymbulak) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #define DEBUG
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long llong;
#define ALL_LL
#ifdef ALL_LL
#define int llong
#endif
pair<int, int> answer(0, 1);
vector<int> nei[200001];
pair<int, int> tx[800000], ty[800000];
template<typename T>
inline T Comb2(T x) { return ((x - (T)1) * x) / (T)2; }
template<class T1, class T2>
ostream& operator<<(ostream& ostr, const pair<T1, T2>& a)
{
return ostr << "{" << a.first << ", " << a.second << "}";
}
void Add(pair<int, int>* a, const pair<int, int>& rhs)
{
if (rhs.first > a->first)
*a = rhs;
else if (rhs.first == a->first)
a->second += rhs.second;
}
namespace Decomp
{
bool used[200001];
bool root[200001];
pair<int, int> ray[200001];
vector<int> line;
int FindCycle(int v, int par)
{
used[v] = true;
for (int to: nei[v])
{
if (to == par) continue;
if (used[to])
{
line.push_back(v);
root[v] = true;
return to;
}
if (int ret = FindCycle(to, v))
{
line.push_back(v);
root[v] = true;
if (v == ret)
return 0;
return ret;
}
}
return 0;
}
void DFS(int v, int par)
{
// cerr << "v: " << v << "\tpar: " << par << endl;
ray[v] = make_pair(0, 1);
for (int to: nei[v])
if (to != par && !root[to])
{
DFS(to, v);
pair<int, int> p = ray[to];
++p.first;
Add(ray + v, p);
}
}
void AddWays(int v, int par)
{
vector<pair<int, int>> chld;
chld.reserve(nei[v].size());
for (int to: nei[v])
if (to != par && !root[to])
{
AddWays(to, v);
chld.push_back({ray[to].first + 1, ray[to].second});
}
if (chld.size() < 2)
return;
sort(chld.begin(), chld.end(), greater<pair<int, int>>());
int i = 2;
while (i < chld.size() && chld[i].first == chld[i - 1].first)
++i;
if (i < chld.size()) chld.erase(chld.begin() + i, chld.end());
/*cerr << "v: " << v << "` chld: ";
for (auto it: chld)
cerr << it << ' ';
cerr << endl;*/
if (chld[0].first == chld[1].first)
{
pair<int, int> cur = {2 * chld[0].first, 0};
int sum = 0;
for (const pair<int, int>& p: chld)
{
cur.second -= Comb2(p.second);
// if (v == 1)
// cerr << "delta -" << Comb2(p.second) << endl;
sum += p.second;
}
cur.second += Comb2(sum);
// if (v == 1)
// cerr << "v: 1, cur: " << cur << endl;
Add(&answer, cur);
}
else
{
int sum = 0;
for (int i = 1; i < chld.size(); ++i)
sum += chld[i].second;
pair<int, int> cur = {chld[0].first + chld[1].first, chld[0].second * sum};
Add(&answer, cur);
}
}
void Decompose(vector<pair<int, int>>* res)
{
FindCycle(1, -1);
#ifdef DEBUG
cerr << line.size() << endl;
for (int v: line)
cerr << v << ' ';
cerr << '\n';
#endif
res->resize(line.size());
for (int i = 0; i < line.size(); ++i)
{
DFS(line[i], -1);
AddWays(line[i], -1);
(*res)[i] = ray[line[i]];
#ifdef DEBUG
cerr << line[i] << ": " << (*res)[i] << '\n';
#endif
}
}
};
void Build(pair<int, int>* t, int v, int vl, int vr, const vector<pair<int, int>>& a)
{
if (vl == vr)
{
t[v] = a[vr];
return;
}
int vm = (vl + vr) / 2;
Build(t, v * 2, vl, vm, a);
Build(t, v * 2 + 1, vm + 1, vr, a);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
pair<int, int> Max(pair<int, int>* t, int v, int vl, int vr, int l, int r)
{
if (vl == l && vr == r)
return t[v];
int vm = (vl + vr) / 2;
if (r <= vm)
return Max(t, v * 2, vl, vm, l, r);
else if (l > vm)
return Max(t, v * 2 + 1, vm + 1, vr, l, r);
return max(Max(t, v * 2, vl, vm, l, vm),
Max(t, v * 2 + 1, vm + 1, vr, vm + 1, r));
}
#ifdef ALL_LL
#undef ALL_LL
#endif // ALL_LL
int main()
#ifdef ALL_LL
#define int llong
#endif // ALL_LL
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int nodes;
cin >> nodes;
for (int i = 0; i < nodes; ++i)
{
int u, v;
cin >> u >> v;
nei[u].push_back(v);
nei[v].push_back(u);
}
vector<pair<int, int>> a;
Decomp::Decompose(&a);
int n = a.size();
vector<pair<int, int>> x(n), y(n);
for (int i = 0; i < n; ++i)
{
x[i] = {i + a[i].first, a[i].second};
y[i] = {n - i + a[i].first, a[i].second};
#ifdef DEBUG
cerr << "i: " << i << ": x = " << x[i] << " y = " << y[i] << " a[i] = " << a[i] << endl;
#endif
}
Build(tx, 1, 0, n - 1, x);
Build(ty, 1, 0, n - 1, y);
for (int l = 0; l + 1 < n; ++l)
{
int s = l + 1;
int e = l + n / 2;
if (n % 2 == 0) --e;
e = min(e, n - 1);
if (s <= e)
{
pair<int, int> mx = Max(tx, 1, 0, n - 1, s, e);
Add(&answer, {mx.first - l + a[l].first, mx.second * a[l].second});
}
s = l + n / 2 + 1;
e = n - 1;
if (s <= e)
{
pair<int, int> mx = Max(ty, 1, 0, n - 1, s, e);
Add(&answer, {mx.first + l + a[l].first, mx.second * a[l].second});
}
if (n % 2 == 0 && l + n / 2 < n)
{
pair<int, int> cur = a[l + n / 2];
Add(&answer, {cur.first + a[l].first + n / 2, 2 * cur.second * a[l].second});
}
}
// cerr << answer.first<< ' ';
cout << answer.second << endl;
}
/*
19
6 2
6 4
1 4
1 5
2 3
6 7
7 8
7 9
6 10
10 11
11 12
8 13
9 14
3 15
10 16
16 17
16 18
2 19
4 19
6
6 2
6 4
1 4
1 5
2 3
2 4
*/