#include <bits/stdc++.h>
using namespace std;
#define ok puts("ok");
#define ll long long
const int N = (int)2e5 + 7;
vector < int > gr[N];
int n;
int used[N];
ll ans = 0;
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);
}
}
}
}
int diam;
vector < int > node;
int deg[N];
int sz[N], isdel[N];
map < int, int > mp1, mp2;
void precalc(int v, int pr) {
sz[v] = 1;
for (int to : gr[v]) {
if (to == pr || used[to] == 2 || isdel[to]) continue;
precalc(to, v);
sz[v] += sz[to];
}
}
int findcentroid(int v) {
int cur = v;
int pr = v;
bool run = 1;
while (run) {
run = 0;
for (int to : gr[cur]) {
if (to == pr || (used[to] == 2) || isdel[to]) continue;
if (sz[to] * 2 >= sz[v]) {
run = 1;
pr = cur;
cur = to;
break;
}
}
}
return cur;
}
int cnt[N][20];
void calc(int v, int pr, int val, int d, int dep) {
cnt[d][dep] += val;
for (int to : gr[v]) {
if (to == pr || used[to] == 2 || isdel[to]) continue;
calc(to, v, val, d + 1, dep);
}
}
ll res;
void calc1(int v, int pr, int d, int dep) {
res += cnt[diam - d][dep];
for (int to : gr[v]) {
if (to == pr || used[to] == 2 || isdel[to]) continue;
calc1(to, v, d + 1, dep);
}
}
void decompose(int v, int dep) {
precalc(v, v);
int cen = findcentroid(v);
isdel[cen] = 1;
calc(cen, cen, 1, 0, dep);
res = 0;
res += cnt[diam][dep];
for (int to : gr[cen]) {
if (isdel[to] || used[to] == 2) continue;
calc(to, cen, -1, 1, dep);
calc1(to, cen, 1, dep);
calc(to, cen, 1, 1, dep);
}
res /= 2;
ans += res;
calc(cen, cen, -1, 0, dep);
for (int to : gr[cen]) {
if (isdel[to] || used[to] == 2) continue;
decompose(to, dep + 1);
}
}
pair < int, int > mxh[N];
void dfs(int v, int pr) {
bool asd = 0;
for (int to : gr[v]) {
if (to == pr || used[to] == 2) continue;
dfs(to, v);
asd = 1;
if (mxh[to].first == mxh[v].first) {
mxh[v].second += mxh[to].second;
} else if (mxh[to].first > mxh[v].first) {
mxh[v] = mxh[to];
}
}
if (!asd) {
mxh[v] = {0, 1};
} else
mxh[v].first++;
}
int us[N];
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);
}
}
main() {
//freopen("shymbulak.in", "r", stdin);
//freopen("shymbulak.out", "w", stdout);
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;
}
}
for (int i = 1; i <= n; i++) {
if (used[i] == 2) {
used[i] = 1;
decompose(i, 0);
dfs(i, 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;
}
}
int h1;
h1 = node.size() / 2;
if (node.size() & 1 ^ 1) h1--;
for (int i = 0; i < h1; i++) {
mp1[-i + mxh[node[i]].first] += mxh[node[i]].second;
}
int cur = h1;
res = 0;
do {
res += mp1[diam - mxh[node[cur]].first - cur] * mxh[node[cur]].second;
int lst = cur - h1;
mp1[-lst + mxh[node[lst]].first] -= mxh[node[lst]].second;
mp1[-cur + mxh[node[cur]].first] += mxh[node[cur]].second;
cur++;
} while((int)cur < node.size());
for (int i = (int)node.size() - h1; i < node.size(); i++) {
mp2[(int)node.size() - i + mxh[node[i]].first] += mxh[node[i]].second;
}
cur = 0;
while (cur < h1) {
res += mp2[diam - mxh[node[cur]].first - cur] * mxh[node[cur]].second;
int lst = cur - h1 + (int)node.size();
mp2[(int)node.size() - lst + mxh[node[lst]].first] -= mxh[node[lst]].second;
mp2[(int)node.size() - cur + mxh[node[cur]].first] += mxh[node[cur]].second;
cur++;
}
assert(res & 1 ^ 1);
ans += res;
res = 0;
if ((int)node.size() & 1 ^ 1) {
h1 = node.size() / 2;
for (int i = 0; i < node.size(); i++) {
int lst = i - h1;
if (lst < 0) lst += (int)node.size();
if (diam - h1 == mxh[node[i]].first + mxh[node[lst]].first) {
res += mxh[node[i]].second * mxh[node[lst]].second;
}
}
ans += res;
}
cout << ans;
}
/*
13
1 2
2 3
3 4
4 5
4 6
3 7
7 8
8 9
3 10
10 11
11 12
12 13
2 4
5
1 2
2 3
3 4
4 1
1 5
ans=2
*/
Compilation message
shymbulak.cpp:139:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:171:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == node.size()) {
~~^~~~~~~~~~~~~~
shymbulak.cpp:207:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if (node.size() & 1 ^ 1) h1--;
~~~~~~~~~~~~^~~
shymbulak.cpp:219:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} while((int)cur < node.size());
~~~~~~~~~^~~~~~~~~~~~~
shymbulak.cpp:220:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = (int)node.size() - h1; i < node.size(); i++) {
~~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from shymbulak.cpp:1:
shymbulak.cpp:231:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
assert(res & 1 ^ 1);
~~~~^~~
shymbulak.cpp:234:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if ((int)node.size() & 1 ^ 1) {
~~~~~~~~~~~~~~~~~^~~
shymbulak.cpp:236:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < node.size(); i++) {
~~^~~~~~~~~~~~~
shymbulak.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
shymbulak.cpp:145: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 |
6 ms |
5752 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6004 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
6040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
252 ms |
17192 KB |
Output is correct |
| 2 |
Correct |
168 ms |
17668 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
23608 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
