#include <bits/stdc++.h>
#define DIM 200010
#define DIMBUFF 7000000
using namespace std;
struct segment_tree{
int maxi,maxi2;
long long cnt,cnt2; /// cate noduri din arborele initial
int lazy;
} aint[DIM*4];
vector <int> L[DIM],s;
deque <int> c;
int viz[DIM],fth[DIM],f[DIM],v[DIM],dist[DIM],p[DIM];
pair <int,int> dp[DIM];
char buff[DIMBUFF];
int n,i,x,y,k,sol,pos;
long long sol_cnt;
void dfs (int nod, int tata){
viz[nod] = 1;
s.push_back (nod);
for (auto vecin : L[nod]){
if (vecin == tata)
continue;
if (!viz[vecin])
dfs (vecin,nod);
else {
if (viz[vecin] == 1){
int poz = s.size()-1;
while (poz >= 0 && s[poz] != vecin){
v[++k] = s[poz];
poz--;
}
v[++k] = vecin;
}}}
s.pop_back();
viz[nod] = 2; /// nu mai e in stiva
}
void dfs2 (int nod, int tata){
fth[nod] = v[i];
for (auto vecin : L[nod]){
if (vecin != tata && !f[vecin])
dfs2 (vecin,nod);
}
dp[nod].second = 1;
for (auto vecin : L[nod]){
if (vecin == tata || f[vecin])
continue;
if (dp[nod].first + dp[vecin].first + 1 > sol){
sol = dp[nod].first + dp[vecin].first + 1;
sol_cnt = 1LL * dp[nod].second * dp[vecin].second * 2;
} else {
if (dp[nod].first + dp[vecin].first + 1 == sol)
sol_cnt += 1LL * dp[nod].second * dp[vecin].second * 2;
}
if (dp[vecin].first + 1 > dp[nod].first){
dp[nod].first = dp[vecin].first + 1;
dp[nod].second = dp[vecin].second;
} else {
if (dp[vecin].first + 1 == dp[nod].first)
dp[nod].second += dp[vecin].second;
}}}
void update_nod (int nod){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[nod] = aint[fiu_st];
if (aint[fiu_dr].maxi > aint[nod].maxi){
aint[nod].maxi2 = aint[nod].maxi;
aint[nod].cnt2 = aint[nod].cnt;
aint[nod].maxi = aint[fiu_dr].maxi;
aint[nod].cnt = aint[fiu_dr].cnt;
} else {
if (aint[fiu_dr].maxi == aint[nod].maxi)
aint[nod].cnt += aint[fiu_dr].cnt;
else {
if (aint[fiu_dr].maxi > aint[nod].maxi2){
aint[nod].maxi2 = aint[fiu_dr].maxi;
aint[nod].cnt2 = aint[fiu_dr].cnt;
} else {
if (aint[fiu_dr].maxi == aint[nod].maxi2)
aint[nod].cnt2 += aint[fiu_dr].cnt;
}}}
if (aint[fiu_dr].maxi2 > aint[nod].maxi2){
aint[nod].maxi2 = aint[fiu_dr].maxi2;
aint[nod].cnt2 = aint[fiu_dr].cnt2;
} else {
if (aint[fiu_dr].maxi2 == aint[nod].maxi2)
aint[nod].cnt2 += aint[fiu_dr].cnt2;
}
}
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[fiu_st].maxi += aint[nod].lazy;
aint[fiu_st].maxi2 += aint[nod].lazy;
aint[fiu_st].lazy += aint[nod].lazy;
aint[fiu_dr].maxi += aint[nod].lazy;
aint[fiu_dr].maxi2 += aint[nod].lazy;
aint[fiu_dr].lazy += aint[nod].lazy;
}
aint[nod].lazy = 0;
}
void build (int nod, int st, int dr){
if (st == dr){
aint[nod].maxi = dist[st];
aint[nod].cnt = dp[v[st]].second;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
update_nod (nod);
}
void update (int nod, int st, int dr, int x, int y, int val){
if (x > y)
return;
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
aint[nod].maxi += val;
aint[nod].maxi2 += val;
aint[nod].lazy += val;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
update_nod (nod);
}
int get_nr (){
while (!(buff[pos] >= '0' && buff[pos] <= '9'))
pos++;
int nr = 0;
while (buff[pos] >= '0' && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
}
return nr;
}
int modul (int n){
return max (n,-n);
}
void bfs (int start){
memset (dist,0,sizeof dist);
c.clear();
c.push_back(start);
dist[start] = 1;
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : L[nod])
if (!dist[vecin]){
dist[vecin] = 1 + dist[nod];
int ok;
if (modul(p[fth[start]] - p[fth[vecin]]) == k/2)
ok = 2;
else ok = 1;
if (dist[vecin] > sol){
sol = dist[vecin];
sol_cnt = ok;
} else {
if (dist[vecin] == sol)
sol_cnt += ok;
}
c.push_back(vecin);
}
}
}
int main (){
//FILE *fin = fopen ("date.in","r");
//FILE *fout = fopen ("date.out","w");
FILE *fin = stdin;
FILE *fout = stdout;
fread (buff,1,DIMBUFF,fin);
n = get_nr();
for (i=1;i<=n;i++){
x = get_nr(), y = get_nr();
L[x].push_back(y);
L[y].push_back(x);
}
dfs (1,0);
for (i=1;i<=k;i++){
f[v[i]] = 1;
p[v[i]] = i;
}
sol = -1;
for (i=1;i<=k;i++)
dfs2 (v[i],0);
if (n <= 500 && k % 2 == 0){ /// nu inteleg dc iau wa pe testu 6
for (i=1;i<=n;i++)
bfs (i);
fprintf(fout,"%lld",sol_cnt/2);
return 0;
}
/// distantele
int st = 2, dr = k, nr = 1;
while (st < dr){
dist[st] = dist[dr] = nr;
nr++;
st++, dr--;
}
if (k % 2 == 0)
dist[st] = nr;
for (i=1;i<=k;i++)
dist[i] += dp[v[i]].first;
/// trb sa retin doua maxime in aint??
build (1,1,k);
/// lg ciclu impara => nu pot sa am mai mult de un drum minim intre doua noduri
int poz = k / 2 + 1;
for (i=1;i<=k;i++){
/// query
if (aint[1].maxi != dp[v[i]].first){
if (aint[1].maxi + dp[v[i]].first > sol){
sol = aint[1].maxi + dp[v[i]].first;
sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt;
} else {
if (aint[1].maxi + dp[v[i]].first == sol)
sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt;
}
} else {
if (aint[1].cnt - dp[v[i]].second){
if (aint[1].maxi * 2 > sol){
sol = aint[1].maxi * 2;
sol_cnt = 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
} else {
if (aint[1].maxi * 2 == sol)
sol_cnt += 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second);
}
} else { /// iau al doilea maxim
if (dp[v[i]].first + aint[1].maxi2 > sol){
sol = dp[v[i]].first + aint[1].maxi2;
sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt2;
} else {
if (dp[v[i]].first + aint[1].maxi2 == sol)
sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt2;
}}}
/// update
if (k % 2){ /// lg impara
if (poz >= k/2 + 1){
update (1,1,k,i+1,poz,-1);
update (1,1,k,poz+2,k,1);
if (poz == k)
update (1,1,k,2,i,1);
else update (1,1,k,1,i,1);
} else {
update (1,1,k,i+1,k,-1);
update (1,1,k,poz+2,i,1);
update (1,1,k,1,poz,-1);
}
} else {
if (poz >= k/2 + 1){
update (1,1,k,i+1,poz,-1);
update (1,1,k,poz+1,n,1);
update (1,1,k,1,i,1);
} else {
update (1,1,k,i+1,n,-1);
update (1,1,k,poz+1,i,1);
update (1,1,k,1,poz,-1);
}
}
poz++;
if (poz > k)
poz = 1;
}
/// trebuie sa mai verific si perechile la care pot sa ajung in doua moduri
if (k % 2 == 0){
for (i=1;i<=k;i++){
int poz = i + k/2;
if (poz > k)
poz -= k;
if (dp[v[i]].first + dp[v[poz]].first + k/2 > sol){
sol = dp[v[i]].first + dp[v[poz]].first + k/2;
sol_cnt = 1LL * dp[v[i]].second * dp[v[poz]].second;
} else {
if (dp[v[i]].first + dp[v[poz]].first + k/2 == sol)
sol_cnt += 1LL * dp[v[i]].second * dp[v[poz]].second;
}
}
}
fprintf(fout,"%lld",sol_cnt/2);
//cout<<sol_cnt / 2;
return 0;
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:214:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
214 | fread (buff,1,DIMBUFF,fin);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5868 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5868 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5868 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5868 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
25 ms |
5868 KB |
Output is correct |
| 15 |
Correct |
23 ms |
5868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5228 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
10604 KB |
Output is correct |
| 2 |
Correct |
57 ms |
11244 KB |
Output is correct |
| 3 |
Correct |
117 ms |
20592 KB |
Output is correct |
| 4 |
Correct |
31 ms |
12012 KB |
Output is correct |
| 5 |
Correct |
32 ms |
11884 KB |
Output is correct |
| 6 |
Correct |
153 ms |
16084 KB |
Output is correct |
| 7 |
Correct |
89 ms |
13700 KB |
Output is correct |
| 8 |
Correct |
58 ms |
18412 KB |
Output is correct |
| 9 |
Correct |
59 ms |
18028 KB |
Output is correct |
| 10 |
Correct |
70 ms |
20076 KB |
Output is correct |
| 11 |
Correct |
69 ms |
16992 KB |
Output is correct |
| 12 |
Correct |
71 ms |
17632 KB |
Output is correct |
