#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <functional>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define pb(a) push_back(a)
#define vi vector<int>
#define ii pair<int,int>
#define iii pair<bool, pair<int,int> >
#define mp(a,b) make_pair(a,b)
struct Edge{
int a;int b;
int ind;
bool bad;
};
using namespace std;
vector<Edge*>* g;
int n;
Edge** edges;
bool* sp_node;
bool* sp_edge;
bool* visited;
int ancestor = -1;
bool ex = false;
int IND__ = 0;
int* index_;
void dfs_cycle(int node,int p){
visited[node] = true;
FOR(i,g[node].size()){
Edge* ed = g[node][i];
int u = ed->a == node?ed->b:ed->a;
if(u == p)continue;
if(visited[u]){
ancestor = u;
if(ex)return;
ed->bad = true;
//ed->ind = IND__++;
index_[node] = IND__++;
}else{
if(ex)return;
dfs_cycle(u,node);
if(ancestor != -1){
if(ancestor == node){
ed->bad = true;
//ed->ind = IND__++;
index_[node] = IND__++;
ex = true;
}
if(ex)return;
ed->bad = true;
//ed->ind = IND__++;
index_[node] = IND__++;
return;
}
}
}
}
ii maxDpthDFS(int node,int p){
ii mx;
mx.first = 0;mx.second = 1;
FOR(i,g[node].size()){
Edge* ed = g[node][i];
int u = ed->a == node?ed->b:ed->a;
if(u == p)continue;
if(ed->bad)continue;
ii val = maxDpthDFS(u,node);
if(val.first > mx.first){
mx.first = val.first;
mx.second = val.second;
}else if(val.first == mx.first){
mx.second+=val.second;
}
}
mx.first++;
return mx;
}
int main(){
cin >> n;
g = new vector<Edge*>[n];
index_= new int[n];
FOR(i,n){
index_[i] = -1;
}
edges = new Edge*[n];
FOR(i,n){
int a,b;
cin >> a >> b;
a--;
b--;
Edge* ed = new Edge();
ed->a = a;
ed->b = b;
ed->bad = false;
edges[i] = ed;
g[a].pb(ed);
g[b].pb(ed);
}
visited = new bool[n];
FOR(i,n)visited[i] = false;
dfs_cycle(0,-1);
//cout << endl<<endl;
//cout <<ancestor<<endl;
//FOR(i,n){
// if(edges[i]->bad){
// cout << edges[i]->a +1<< " " << edges[i]->b + 1<<endl;
// }
//}
sp_node = new bool[n];
sp_edge = new bool[n];
FOR(i,n)sp_node[i] = sp_edge[i] = false;
FOR(i,n){
if(edges[i]->bad){
sp_node[edges[i]->a] = sp_node[edges[i]->b] = true;
sp_edge[i] = true;
}
}
//cout << "hell0" <<endl;
ii vals[n];
FOR(i,n)vals[i].first = vals[i].second = 0;
FOR(i,n){
if(sp_node[i])vals[i] = maxDpthDFS(i,-1);
}
//cout << IND__ <<endl;
ii all[IND__*3];
//IND__ = 0;
FOR(i,n){
// cout << edges[i]->a << " "<<edges[i]->b << " " <<edges[i]->bad << " " <<edges[i]->ind<<endl;
}
FOR(i,n){
if(sp_node[i]){
all[index_[i]+IND__*2] = all[index_[i]+IND__] = all[index_[i]] = vals[i];
}
}
/*
FOR(i,n){
cout << vals[i].first << " " << vals[i].second <<endl;
}
cout <<endl;
FOR(i,3*IND__){
cout << all[i].first << " "<<all[i].second <<endl;
}*/
int mx=0;int ctr=0;
int cnt = IND__/2;
//cout << "cnt : "<<cnt<<endl;
FOR(i,IND__){
int st = IND__ + i;
i+=IND__;
FORE(j,1,cnt){
if(all[i].first + all[i+j].first + j-1 > mx){
mx= all[i].first + all[i+j].first + j-1;
ctr = all[i].second*all[i+j].second;
}else if(all[i].first + all[i+j].first + j-1 == mx){
ctr += all[i].second*all[i+j].second;
}
if(all[i].first + all[i-j].first + j-1 > mx){
mx= all[i].first + all[i-j].first + j-1;
ctr = all[i].second*all[i-j].second;
}else if(all[i].first + all[i-j].first + j-1 == mx){
ctr += all[i].second*all[i-j].second;
}
}
//cout << mx << " =----= "<<ctr <<endl;
i-=IND__;
}
// cout << mx <<endl;
cout << ctr/2 <<endl;
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs_cycle(int, int)':
shymbulak.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
shymbulak.cpp:41:7:
FOR(i,g[node].size()){
~~~~~~~~~~~~~~~~
shymbulak.cpp:41:3: note: in expansion of macro 'FOR'
FOR(i,g[node].size()){
^~~
shymbulak.cpp: In function 'std::pair<int, int> maxDpthDFS(int, int)':
shymbulak.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
shymbulak.cpp:76:7:
FOR(i,g[node].size()){
~~~~~~~~~~~~~~~~
shymbulak.cpp:76:3: note: in expansion of macro 'FOR'
FOR(i,g[node].size()){
^~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:163:9: warning: unused variable 'st' [-Wunused-variable]
int st = IND__ + i;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
728 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
12824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
