#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int MAXM = 2e5;
const int treeMAXN = 2e5; // n bccs, n cut nodes
typedef long long ll;
vector<int> tree_edges[treeMAXN];
vector<int> edges[MAXN];
int n, m;
vector<int> cut_verts;
bool is_cut[MAXN];
int depth[MAXN];
int lp[MAXN];
vector<int> bccs_in[MAXN];
int bcc_sz[treeMAXN];
int t = 0;
bool vis[treeMAXN];
ll ans = 0;
int rt;
vector<int> cent_graph[treeMAXN];
int sz[treeMAXN];
vector<int> in_decomp;
vector<int> in_stree[treeMAXN];
ll smult[treeMAXN];
ll psum[treeMAXN];
void print(vector<int> &v) {
for (int i: v) {
cout << i << " ";
}
cout << endl;
}
void find_cut(int i, int p = -1) {
lp[i] = depth[i];
int c = 0;
bool is_point = 0;
for (int next: edges[i]) {
if (next == p) continue;
if (depth[next] != -1) {
lp[i] = min(lp[i], depth[next]);
continue;
}
c++;
depth[next] = 1+depth[i];
find_cut(next, i);
lp[i] = min(lp[i], lp[next]);
if (lp[next] >= depth[i]) is_point = 1;
}
if (i == 0) {
if (c > 1) {
cut_verts.push_back(i);
is_cut[i] = 1;
}
}
else if (is_point) {
cut_verts.push_back(i);
is_cut[i] = 1;
}
}
void make_bcc(int s) {
vis[s] = 1;
bcc_sz[t]++;
for (int next: edges[s]) {
if (vis[next]) continue;
if (is_cut[next]) {
bccs_in[next].push_back(t);
continue;
}
make_bcc(next);
}
}
void make_sz(int cur, int p = -1) {
sz[cur] = 1;
for (int next: tree_edges[cur]) {
if (vis[next] || next == p) continue;
make_sz(next, cur);
sz[cur] += sz[next];
}
}
int make_decomp(int cur) {
make_sz(cur);
int tot = sz[cur];
bool f = 1;
int p = -1;
while (f) {
f = 0;
for (int next: tree_edges[cur]) {
if (vis[next] || next == p) continue;
if (sz[next] > tot/2) {
p = cur;
cur = next;
f = 1;
break;
}
}
}
vis[cur] = 1;
for (int next: tree_edges[cur]) {
if (!vis[next]) cent_graph[cur].push_back(make_decomp(next));
}
return cur;
}
void dfs(int cur, int p, ll rtsum, int stree) {
rtsum += bcc_sz[cur];
ll cval = bcc_sz[cur];
smult[cur] = cval*rtsum;
psum[cur] = cval;
in_decomp.push_back(cur);
in_stree[stree].push_back(cur);
for (int next: tree_edges[cur]) {
if (vis[next] || next == p) continue;
dfs(next, cur, rtsum, stree);
}
}
void make_ans(int cur) {
vis[cur] = 1;
in_decomp.clear();
in_decomp.push_back(cur);
ll rtval = bcc_sz[cur];
smult[cur] = rtval*rtval;
psum[cur] = rtval;
for (int next: tree_edges[cur]) {
if (vis[next]) continue;
dfs(next, cur, rtval, next);
//cout << next << endl;
//print(in_stree[next]);
}
//print(in_decomp);
ll s = 0;
ll p = 0;
ll q = 0;
for (int v: in_decomp) {
s += smult[v];
p += psum[v];
q += psum[v]*psum[v];
}
//cout << s << ' ' << p << ' ' << q << endl;
ll add = 2*s*p-p*p*rtval-2*p*q+rtval*rtval*rtval;
for (int next: tree_edges[cur]) {
if (vis[next]) continue;
s = 0;
p = 0;
q = 0;
for (int v: in_stree[next]) {
s += smult[v];
p += psum[v];
q += psum[v]*psum[v];
}
add -= 2*s*p-p*p*rtval-2*p*q;
}
//cout << add << endl << endl;
ans += add;
for (int next: cent_graph[cur]) make_ans(next);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n-1; i++) {
int x, y; cin >> x >> y; x--; y--;
edges[x].push_back(y);
edges[y].push_back(x);
}
fill(depth, depth+n, -1);
depth[0] = 0;
find_cut(0);
for (int i = 0; i < n; i++) {
if (is_cut[i]) continue;
make_bcc(i); t++;
}
assert(t+cut_verts.size() <= treeMAXN);
map<int, int> pos_of;
int d = 0;
for (int v: cut_verts) {
pos_of[v] = d;
d++;
}
for (int v: cut_verts) {
for (int next: edges[v]) {
if (is_cut[next]) tree_edges[pos_of[v]+t].push_back(pos_of[next]+t);
}
for (int next: bccs_in[v]) {
tree_edges[pos_of[v]+t].push_back(next);
tree_edges[next].push_back(pos_of[v]+t);
}
bcc_sz[pos_of[v]+t] = 1;
}
n = t+cut_verts.size();
//for (int i = 0; i < n; i++) print(tree_edges[i]);
fill(vis, vis+n, 0);
rt = make_decomp(0);
fill(vis, vis+n, 0);
make_ans(rt);
ll p2sum = 0;
ll over_sum = 0;
ll ex = 0;
for (int i = 0; i < n; i++) {
ll cur = bcc_sz[i];
p2sum += cur*(cur-1);
over_sum += cur;
ex += 2*cur*(cur-1);
}
ans += p2sum*over_sum-ex;
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
268 ms |
53772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
41700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
197 ms |
41740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
