#include<bits/stdc++.h>
using namespace::std;
const int N = 200000 + 5;
struct MaxStack{
stack<pair<pair<int, int>, pair<int, int>>> S;
MaxStack(){}
void emplace(pair<int, int> x){
pair<int, int> maximum = x;
if(S.empty()) S.emplace(make_pair(x, maximum));
else{
if(maximum.first == S.top().second.first){
maximum.second += S.top().second.second;
}
else if(maximum.first < S.top().second.first){
maximum = S.top().second;
}
S.emplace(make_pair(x, maximum));
}
}
bool empty(){
return S.empty();
}
pair<int, int> top(){
return S.top().first;
}
pair<int, int> get_max(){
return S.empty() ? make_pair(-1000000000, 0) : S.top().second;
}
void pop(){
S.pop();
}
};
struct MaxQueue{
MaxStack in, out;
void emplace(pair<int, int> x){
in.emplace(x);
}
void pop(){
if(out.empty()){
while(!in.empty()){
pair<int, int> x = in.top(); in.pop();
out.emplace(x);
}
}
out.pop();
}
pair<int, int> get_max(){
pair<int, int> max_in = in.get_max();
pair<int, int> max_out = out.get_max();
if(max_in.first < max_out.first) max_in = max_out;
else if(max_in.first == max_out.first) max_in.second += max_out.second;
return max_in;
}
};
int n;
int h[N];
int cnt[N];
int deg[N];
int best_h[N];
bool cycle[N];
int furthest[N];
vector<int> G[N];
long long memo[N];
vector<int> nodes_in_cycle;
void mark_cycle(){
queue<int> Q;
for(int i = 1; i <= n; i++) cycle[i] = true;
for(int i = 1; i <= n; i++){
if(deg[i] == 1){
Q.emplace(i);
cycle[i] = false;
deg[i] = 0;
}
}
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int v : G[u]){
deg[v]--;
if(deg[v] == 1){
Q.emplace(v);
cycle[v] = false;
}
}
}
}
void compute(int u, int p = -1){
h[u] = best_h[u] = 0;
cnt[u] = 1;
for(int v : G[u]){
if(v == p or cycle[v]) continue;
h[v] = h[u] + 1;
compute(v, u);
if(best_h[v] + 1 == best_h[u]){
cnt[u] += cnt[v];
}
else if(best_h[v] + 1 > best_h[u]){
best_h[u] = best_h[v] + 1;
cnt[u] = cnt[v];
}
}
}
void get_nodes_in_cycle(){
for(int i = 1; i <= n; i++){
if(cycle[i]){
stack<int> Q;
Q.emplace(i);
cycle[i] = false;
while(!Q.empty()){
int u = Q.top(); Q.pop();
nodes_in_cycle.emplace_back(u);
for(int v : G[u]){
if(cycle[v]){
Q.emplace(v);
cycle[v] = false;
}
}
}
break;
}
}
}
void compute_ranges(int k){
MaxQueue r;
for(int i = 0; i <= k; i++){
int x = nodes_in_cycle[i];
r.emplace(make_pair(best_h[x] + i, cnt[x]));
}
for(int i = 0; i < nodes_in_cycle.size(); i++){
int x = nodes_in_cycle[i];
r.pop();
pair<int, int> right_best = r.get_max();
right_best.first -= i - best_h[x];
if(furthest[x] == right_best.first) memo[x] += right_best.second;
else if(furthest[x] < right_best.first){
furthest[x] = right_best.first;
memo[x] = right_best.second;
}
int j = i + k + 1;
int y = nodes_in_cycle[j % nodes_in_cycle.size()];
r.emplace(make_pair(best_h[y] + j, cnt[y]));
}
}
long long get_best(){
int L = nodes_in_cycle.size() / 2;
compute_ranges(L);
reverse(nodes_in_cycle.begin(), nodes_in_cycle.end());
compute_ranges(L);
int best_len = 0;
long long ans = 0;
for(int i = 1; i <= n; i++){
if(furthest[i] == best_len) ans += 1ll * memo[i] * cnt[i];
else if(furthest[i] > best_len){
ans = 1ll * memo[i] * cnt[i];
best_len = furthest[i];
}
}
return ans;
}
long long solve(){
mark_cycle();
for(int i = 1; i <= n; i++) if(cycle[i]) compute(i);
get_nodes_in_cycle();
return get_best() >> 1;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int u, v;
scanf("%d %d", &u, &v);
G[u].emplace_back(v);
G[v].emplace_back(u);
deg[u]++; deg[v]++;
}
printf("%lld\n", solve());
return 0;
}
Compilation message
shymbulak.cpp: In function 'void compute_ranges(int)':
shymbulak.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 0; i < nodes_in_cycle.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
shymbulak.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
189 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
