#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int low[DIM],niv[DIM],f[DIM],st[DIM],elem,sol;
int w[DIM];
vector <int> v[DIM],s[DIM];
pair <int , long long> lnt[DIM];
pair <int , long long> diam[DIM];
pair <int , long long> aint[DIM];
int lzy[DIM];
void dfs (int nod,int tata){
int i,vecin;
low[nod]=niv[nod];
st[++elem]=nod;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tata){
if (!niv[vecin]){
niv[vecin]=1+niv[nod];
dfs (vecin,nod);
low[nod]=min(low[nod],low[vecin]);
///VERIFICARE
if (low[vecin]>=niv[nod]){
sol++;
do{
s[sol].push_back(st[elem]);
elem--;
}while (st[elem+1]!=vecin);
s[sol].push_back(nod);
}
}
else low[nod]=min(low[nod],niv[vecin]);
}
}
}
void dfs2 (int nod , int tt){
int i , vecin;
int maxi1 = 0 , maxi2 = 0 , fmaxi1 = 1 , fmaxi2 = 1 , n1 = 1 , n2 = 1;
long long opt = 1;
/// first e lantul maxim , second e diametrul max din subarb
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (f[vecin] || vecin == tt)
continue; /// nu
dfs2(vecin , nod);
if (lnt[vecin].first > maxi1){
maxi2 = maxi1;
fmaxi2 = fmaxi1;
n2 = n1;
maxi1 = lnt[vecin].first;
fmaxi1 = lnt[vecin].second;
n1 = 1;
opt = lnt[vecin].second;
}
else if (lnt[vecin].first == maxi1){
fmaxi1 += lnt[vecin].second;
n1++;
opt *= lnt[vecin].second;
}
else if (lnt[vecin].first > maxi2){
maxi2 = lnt[vecin].first;
fmaxi2 = lnt[vecin].second;
n2 = 1;
}
else if (lnt[vecin].first == maxi2){
fmaxi2 += lnt[vecin].second;
n2++;
}
}
lnt[nod] = make_pair(maxi1 + 1 , fmaxi1);
if (n1 != 1)
diam[nod] = make_pair(2 * maxi1 + 1 , opt);
else diam[nod] = make_pair(maxi1 + maxi2 + 1 , fmaxi1 * fmaxi2);
}
inline void lazy_update (int nod,int st,int dr){
if (!lzy[nod]) /// nu ii trb lazy
return;
if (st<dr){ /// nu e frunza
lzy[2*nod]+=lzy[nod]; /// pass lazy
lzy[2*nod+1]+=lzy[nod];
}
aint[nod].first+=lzy[nod];
lzy[nod]=0;
}
void build (int nod , int st , int dr , int len){
int mid = (st + dr) / 2;
if (st == dr){
aint[nod] = make_pair(lnt[w[st]].first + min(st - 1 , len - st + 1) , lnt[w[st]].second);
return;
}
build (2 * nod , st , mid , len);
build (2 * nod + 1 , mid + 1 , dr , len);
if (aint[2 * nod].first > aint[2 * nod].second)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod].second)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
int solmax;
long long nr;
void query (int nod , int st , int dr , int l , int r , int start){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (l <= st && dr <= r){
if (solmax < aint[nod].first + lnt[w[start]].first - 1){
solmax = aint[nod].first + lnt[w[start]].first - 1;
nr = aint[nod].second * lnt[w[start]].second;
}
else if (solmax == aint[nod].first + lnt[w[start]].first - 1)
nr += aint[nod].second * lnt[w[start]].second;
return;
}
if (l <= mid)
query(2 * nod , st , mid , l , r , start);
if (mid + 1 <= r)
query(2 * nod + 1 , mid + 1 ,dr , l , r , start);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
}
void update (int nod , int st , int dr , int l , int r , int val){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (l <= st && dr <= r){
lzy[nod] += val;
lazy_update (nod,st,dr);
return;
}
if (l <= mid)
update(2 * nod , st , mid , l , r , val);
if (mid + 1 <= r)
update(2 * nod + 1 , mid + 1 ,dr , l , r , val);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
if (aint[2 * nod].first > aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
void upd_fr (int nod , int st , int dr ,int x , int val){
int mid = (st + dr) / 2;
lazy_update (nod,st,dr);
if (st == dr){
if (val == 1)
aint[nod].second *= 2;
else aint[nod].second /= 2;
return;
}
if (x <= mid)
upd_fr(2 * nod , st , mid , x , val);
else upd_fr(2 * nod + 1 , mid + 1 ,dr , x , val);
lazy_update (2*nod,st,mid);
lazy_update (2*nod+1,mid+1,dr);
if (aint[2 * nod].first > aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod];
else if (aint[2 * nod].first < aint[2 * nod + 1].first)
aint[nod] = aint[2 * nod + 1];
else aint[nod] = make_pair(aint[2 * nod].first , aint[2 * nod].second + aint[2 * nod + 1].second);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , x , y , i , dmax , j , len , middle , nod;
long long frq;
fscanf (fin,"%d",&n);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
/// pasul 1: gaseste ciclul
for (i=1;i<=n;i++){
if (!niv[i]){
niv[i]=1;
dfs (i,0);
}
}
/// comp biconexa cu + 2 noduri
for (i = 1 ; i <= sol ; i++){
if (s[i].size() > 2){ /// asta !!
for (j = 0 ; j < s[i].size() ; j++){
w[j + 1] = s[i][j];
f[s[i][j]] = 1;
}
len = s[i].size();
}
}
/// pt fiecare nod din ciclu, construiesti diametrul + lantul maxim
dmax = 0;
frq = 0;
for (i = 1 ; i <= len ; i++){
dfs2 (w[i] , 0);
if (dmax < diam[w[i]].first){
frq = diam[w[i]].second;
dmax = diam[w[i]].first;
}
else if (dmax == diam[w[i]].first)
frq += diam[w[i]].second;
}
build (1 , 1 , len , len);
/// daca distamta maxima = diametru maxim, mai adaugi si frq
solmax = 0;
nr = 0;
if (len % 2 == 0){ /// cazul cand middle are 2 frecvente
upd_fr (1 , 1 , len , 1 + len / 2 , 1);
query (1 , 1 , len , 2 , len , 1);
middle = 1 + len / 2;
for (i = 2 ; i <= len ; i++){
/// updatezi intervale
nod = i;
middle++;
if (middle > len)
upd_fr (1 , 1 , len , middle - len , 1);
else
upd_fr (1 , 1 , len , middle , 1);
if (middle - 1 > len)
upd_fr (1 , 1 , len , middle - 1 - len , -1);
else
upd_fr (1 , 1 , len , middle - 1 , -1);
/// intre nod si middle - 1 scazi 1
if (middle - 1 < len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
update (1 , 1 , len , middle , len , 1);
}
else if (middle - 1 == len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else {
update (1 , 1 , len , nod , len , -1);
update (1 , 1 , len , 1 , middle - 1 - len , -1);
update (1 , 1 , len , middle - len , nod - 1 , 1);
}
/// query
query (1 , 1 , len , 1 , i - 1 , i);
if (i != len)
query (1 , 1 , len , i + 1 , len , i);
}
}
else {
query (1 , 1 , len , 2 , len , 1);
middle = len / 2 + 1;
for (i = 2 ; i <= len ; i++){
/// updatezi intervale
nod = i;
middle++;
if (middle == len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else if (middle == len + 1){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , 2 , nod - 1 , 1);
}
else if (middle < len){
update (1 , 1 , len , nod , middle - 1 , -1);
update (1 , 1 , len , middle + 1 , len , 1);
update (1 , 1 , len , 1 , nod - 1 , 1);
}
else {
update (1 , 1 , len , nod , len , -1);
update (1 , 1 , len , 1 , middle - 1 - len , -1);
update (1 , 1 , len , middle + 1 - len , nod - 1 , 1);
}
/// query
query (1 , 1 , len , 1 , i - 1 , i);
if (i != len)
query (1 , 1 , len , i + 1 , len , i);
}
}
nr /= 2;
if (solmax == dmax)
nr += frq;
else if (solmax < dmax)
nr = frq;
fprintf (fout,"%lld",nr);
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (i=0;i<v[nod].size();i++){
| ~^~~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (i = 0 ; i < v[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:238:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
238 | for (j = 0 ; j < s[i].size() ; j++){
| ~~^~~~~~~~~~~~~
shymbulak.cpp:216:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
216 | fscanf (fin,"%d",&n);
| ~~~~~~~^~~~~~~~~~~~~
shymbulak.cpp:218:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
218 | fscanf (fin,"%d%d",&x,&y);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:319:13: warning: 'len' may be used uninitialized in this function [-Wmaybe-uninitialized]
319 | if (i != len)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9708 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
20588 KB |
Output is correct |
| 2 |
Incorrect |
116 ms |
21356 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
