#include <bits/stdc++.h>
using namespace std;
#define ll 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);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int u, v;
scanf("%d %d", &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(int)':
shymbulak.cpp:39:6: warning: unused variable 'asd' [-Wunused-variable]
int asd = v;
^~~
shymbulak.cpp: At global scope:
shymbulak.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:119:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == node.size()) {
~~^~~~~~~~~~~~~~
shymbulak.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
9 ms |
7508 KB |
Output is correct |
| 6 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
8 ms |
7508 KB |
Output is correct |
| 9 |
Correct |
8 ms |
7628 KB |
Output is correct |
| 10 |
Correct |
8 ms |
7628 KB |
Output is correct |
| 11 |
Correct |
9 ms |
7672 KB |
Output is correct |
| 12 |
Correct |
8 ms |
7676 KB |
Output is correct |
| 13 |
Correct |
14 ms |
7684 KB |
Output is correct |
| 14 |
Correct |
31 ms |
7688 KB |
Output is correct |
| 15 |
Incorrect |
30 ms |
7944 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
7944 KB |
Output is correct |
| 2 |
Correct |
41 ms |
7944 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
7944 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1545 ms |
11548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
