#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = (int)2e5 + 7;
vector < int > gr[N];
int n;
int used[N], deg[N];
ll ans = 0;
int diam;
int dist[N], us[N], id[N];
vector < int > node;
void bfs(int v) {
memset(used, 0, sizeof used);
queue < int > q;
q.push(v);
used[v] = 1;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : gr[v]) {
if (used[to] == 0) {
used[to] = used[v] + 1;
q.push(to);
}
}
}
}
void bfs1(int v) {
memset(dist, 0, sizeof dist);
queue < int > q;
q.push(v);
dist[v] = 1;
int asd = v;
int res = 0;
int mx = 0;
while (!q.empty()) {
v = q.front();
q.pop();
for (int to : gr[v]) {
if (dist[to] == 0) {
dist[to] = dist[v] + 1;
mx = max(mx, dist[to]);
q.push(to);
} else if (dist[v] + 1 == dist[to]) {
res = id[to];
}
}
}
if (mx - 1 == diam) {
int val = 0;
for (int i = 1; i <= n; i++) {
if (mx == dist[i]) val++;
}
ans += val;
if (res) {
val = 0;
for (int i = 1; i <= n; i++) {
if (id[i] == res && dist[i] == mx) val++;
}
ans += val;
}
}
}
void dfs1(int v, int pr) {
node.push_back(v);
us[v] = 1;
for (int to : gr[v]) {
if (us[to] || used[to] != 2) continue;
dfs1(to, v);
}
}
void dfs2(int v, int pr) {
for (int to : gr[v]) {
if (to == pr || used[to] == 2) continue;
id[to] = id[v];
dfs2(to, v);
}
}
main() {
iota(id, id + N, 0);
cin >> n;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
gr[u].push_back(v);
gr[v].push_back(u);
deg[u]++;
deg[v]++;
}
int mx = 0;
bfs(1);
for (int i = 1; i <= n; i++) {
if (used[i] > used[mx]) mx = i;
}
bfs(mx);
mx = 0;
for (int i = 1; i <= n; i++) {
if (used[i] > used[mx]) {
mx = i;
}
}
diam = used[mx] - 1;
for (int i = 1; i <= n; i++) {
if (gr[i].size() == 1) {
node.push_back(i);
}
}
memset(used, 0, sizeof used);
for (int i = 0; i < n; i++) {
if (i == node.size()) {
break;
}
int v = node[i];
used[v] = 1;
for (int to : gr[v]) {
if (!used[to]) {
deg[to]--;
if (deg[to] <= 1) {
node.push_back(to);
}
}
}
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
used[i] = 2;
}
}
while (!node.empty()) node.pop_back();
for (int i = 1; i <= n; i++) {
if (used[i] == 2) {
dfs1(i, i);
break;
}
}
for (int i = 1; i <= n; i++) {
if (used[i] == 2) {
dfs2(i, i);
}
}
for (int i = 1; i <= n; i++) {
bfs1(i);
}
cout << ans / 2;
}
Compilation message
shymbulak.cpp: In function 'void bfs1(long long int)':
shymbulak.cpp:40:6: warning: unused variable 'asd' [-Wunused-variable]
int asd = v;
^~~
shymbulak.cpp: At global scope:
shymbulak.cpp:89:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:120:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == node.size()) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9852 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9852 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9972 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 7 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 8 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 9 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 11 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9972 KB |
Output is correct |
| 13 |
Correct |
22 ms |
9972 KB |
Output is correct |
| 14 |
Correct |
50 ms |
9972 KB |
Output is correct |
| 15 |
Incorrect |
51 ms |
9972 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
10064 KB |
Output is correct |
| 2 |
Correct |
72 ms |
10064 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
10064 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
15800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
