/// stiu ca probabil nu e bn
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
struct segment_tree{
int maxi,lazy;
vector <int> v;
} aint[DIM*4];
vector <int> L[DIM];
vector <pair<int,int> > w;
int viz[DIM],fth[DIM],f[DIM],v[DIM],dist[DIM];
pair <int,int> dp[DIM];
int n,i,x,y,k,sol,sol_cnt;
void dfs (int nod, int tata){
if (k)
return;
viz[nod] = 1;
fth[nod] = tata;
for (auto vecin : L[nod]){
if (k)
return;
if (!viz[vecin])
dfs (vecin,nod);
else {
if (vecin != tata){
int x = nod;
while (x != vecin){
v[++k] = x;
x = fth[x];
}
v[++k] = vecin;
return;
}}}}
void dfs2 (int nod, int tata){
for (auto vecin : L[nod]){
if (vecin != tata && !f[vecin])
dfs2 (vecin,nod);
}
int maxi = 0, maxi2 = 0, cnt = 0, cnt2 = 0;
w.clear();
dp[nod].second = 1;
for (auto vecin : L[nod]){
if (vecin == tata || f[vecin])
continue;
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;
}
w.push_back(make_pair(dp[vecin].first+1,dp[vecin].second));
/*if (dp[vecin].first + 1 > maxi){
maxi2 = maxi, cnt2 = cnt;
maxi = dp[vecin].first + 1, cnt = dp[vecin].second;
} else {
if (dp[vecin].first + 1 == maxi)
cnt += dp[vecin].second;
else {
if (dp[vecin].first + 1 > maxi2){
maxi2 = dp[vecin].first + 1;
cnt2 = dp[vecin].second;
} else {
if (dp[vecin].first + 1 == maxi2)
cnt += dp[vecin].second;
}
}
}
*/
}
/// verific si drumurile care au lca in nod
sort (w.begin(),w.end());
if (w.size() >= 2){
int val = w.back().first, cnt = w.back().second, nr = 0;
for (int i=w.size()-2;i>=0;i--){
if (w[i].first == val){
nr += cnt * w[i].second;
cnt += w[i].second;
} else break;
}
if (nr){
if (val * 2 > sol)
sol = val * 2, sol_cnt = nr * 2; /// numar perechile de doua ori
else {
if (val * 2 == sol)
sol_cnt += nr * 2;
}
} else {
int cnt = 0, val = w[w.size()-2].first;
for (i=w.size()-2;i>=0;i--){
if (w[i].first == val)
cnt += w[i].second;
else break;
}
if (w.back().first + val > sol){
sol = w.back().first + val;
sol_cnt = w.back().second * cnt * 2;
} else {
if (w.back().first + val == sol)
sol_cnt += w.back().second * cnt * 2;
}}}}
void update_nod (int nod){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
if (aint[fiu_st].maxi > aint[fiu_dr].maxi)
aint[nod] = aint[fiu_st];
else {
if (aint[fiu_st].maxi < aint[fiu_dr].maxi)
aint[nod] = aint[fiu_dr];
else {
aint[nod] = aint[fiu_st];
for (auto it : aint[fiu_dr].v)
aint[nod].v.push_back(it);
}}}
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].lazy += aint[nod].lazy;
aint[fiu_dr].maxi += 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].v.push_back(st);
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].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 main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++){
cin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs (1,0);
for (i=1;i<=k;i++)
f[v[i]] = 1;
for (i=1;i<=k;i++)
dfs2 (v[i],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);
if (k % 2){ /// 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
for (auto it : aint[1].v){
if (it == i)
continue;
if (aint[1].maxi + dp[v[i]].first > sol){
sol = aint[1].maxi + dp[v[i]].first;
sol_cnt = dp[v[i]].second * dp[v[it]].second;
} else {
if (aint[1].maxi + dp[v[i]].first == sol)
sol_cnt += dp[v[i]].second * dp[v[it]].second;
}
}
/// update
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);
}
poz++;
if (poz > k)
poz = 1;
}
} else { /// lg para
int poz = k/2 + 1;
for (i=1;i<=k;i++){
/// query
for (auto it : aint[1].v){
if (it == i)
continue;
int ok = (it == poz) ? (2) : (1);
if (aint[1].maxi + dp[v[i]].first > sol){
sol = aint[1].maxi + dp[v[i]].first;
sol_cnt = dp[v[i]].second * dp[v[it]].second * ok;
} else {
if (aint[1].maxi + dp[v[i]].first == sol)
sol_cnt += dp[v[i]].second * dp[v[it]].second * ok;
}
}
/// update
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;
}
}
cout<<sol_cnt / 2;
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs2(int, int)':
shymbulak.cpp:47:9: warning: unused variable 'maxi' [-Wunused-variable]
47 | int maxi = 0, maxi2 = 0, cnt = 0, cnt2 = 0;
| ^~~~
shymbulak.cpp:47:19: warning: unused variable 'maxi2' [-Wunused-variable]
47 | int maxi = 0, maxi2 = 0, cnt = 0, cnt2 = 0;
| ^~~~~
shymbulak.cpp:47:30: warning: unused variable 'cnt' [-Wunused-variable]
47 | int maxi = 0, maxi2 = 0, cnt = 0, cnt2 = 0;
| ^~~
shymbulak.cpp:47:39: warning: unused variable 'cnt2' [-Wunused-variable]
47 | int maxi = 0, maxi2 = 0, cnt = 0, cnt2 = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
30060 KB |
Output is correct |
| 2 |
Correct |
20 ms |
30060 KB |
Output is correct |
| 3 |
Correct |
20 ms |
30060 KB |
Output is correct |
| 4 |
Correct |
20 ms |
30060 KB |
Output is correct |
| 5 |
Correct |
20 ms |
30060 KB |
Output is correct |
| 6 |
Incorrect |
19 ms |
30060 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
30188 KB |
Output is correct |
| 2 |
Correct |
22 ms |
30188 KB |
Output is correct |
| 3 |
Execution timed out |
1583 ms |
30188 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1557 ms |
35692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
