Link
不太知道为什么评黑。
Sub1
用 \(O(N^3)\) 的时间复杂度维护邻接矩阵，然后考虑一个点作为 \(b\) 对答案的贡献，应该是 \(deg_u*(deg_u-1)\)。
Sub2
用 bitset 维护上面的东西能卡过去，时间复杂度 \(O(\frac{N^3}{\omega})\)。
Sub3
考虑目前算法的瓶颈在哪里，应该是我们删点的时候不能快速维护邻接信息。
考虑一下能不能拆点算贡献，即将一条边 \((u_i,v_i)\) 拆成 \((u_i,n+i)\) 和 \((n+i,v_i)\)。
这样将一条边拆开后，我们的一次删除等价于将这个点周围的所有虚点（即编号大于 \(n\) 的点）合并起来。
这样非常好啊。
考虑刻画原来要求的信息。
我们来设 \(x\) 链接 \(a,b\)。\(y\) 链接 \(b,c\)。
- \(x=y\)
贡献为 \(cnt_x(cnt_x +1)(cnt_x-1)\)，条件为 \(x\) 是 \(b\) 的儿子。 - \(x\not= y\) 且都是 \(b\) 的儿子
贡献为 \((\sum\limits_{x}cnt_x)^2-\sum\limits_{x}cnt_x^2\)，条件为 \(x\) 为 \(b\) 的儿子。 - \(\text{otherwise}\)
贡献为 \(2cnt_x\sum\limits_{b}\sum\limits_{y} cnt_y\)，条件为 \(b\) 是 \(x\) 的儿子，\(y\) 是 \(b\) 的儿子。
考虑如何动态更新这个东西，观察到我们删除一个实点，会将周围的虚点合并，并且会影响到这个实点的父亲，父亲的父亲，改一下要维护的和就行。
Code
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 4e5 + 5;
vector<int> vec[N];
int n, ff[N], fa[N];
ll sum1[N], sum2[N], ans;
int find(int x) {return x == ff[x] ? x : ff[x] = find(ff[x]);
}
void dfs(int u) {for (auto v : vec[u]) {if (v == fa[u]) continue;fa[v] = u;dfs(v);if (u <= n)sum1[u] += sum1[v];else {++sum1[u];sum2[u] += sum1[v];}}
}
ll f(ll x) {return x * x * x - x * x - x;
}
int main() {FASTIO;freopen("last.in", "r", stdin);freopen("last.out", "w", stdout);cin >> n;for (int i = 1; i < n; ++i) {int u, v; cin >> u >> v;vec[u].push_back(n + i);vec[n + i].push_back(u);vec[v].push_back(n + i);vec[n + i].push_back(v);}for (int i = 1; i <= n * 2; ++i) ff[i] = i;dfs(n);for (int i = 1; i <= n; ++i) ans += sum1[i] * sum1[i];for (int i = n + 1; i < 2 * n; ++i) ans += f(sum1[i]) + 2 * sum1[i] * sum2[i];for (int u = 1; u <= n; ++u) {cout << ans << '\n';int g = find(fa[u]);int w = fa[g];ll del = -1;ans -= f(sum1[g]) + 2 * sum1[g] * sum2[g] + sum1[w] * sum1[w];sum1[w] -= sum1[g];--sum1[g];sum2[g] -= sum1[u];ans -= sum1[u] * sum1[u];sum1[u] = 0;for (auto v : vec[u]) {if (v == fa[u]) continue;ff[v] = g;sum1[g] += sum1[v];sum2[g] += sum2[v];del += sum1[v];ans -= f(sum1[v]) + 2 * sum1[v] * sum2[v];sum1[v] = sum2[v] = 0;}sum1[w] += sum1[g];ans += f(sum1[g]) + 2 * sum1[g] * sum2[g] + sum1[w] * sum1[w];w = find(fa[fa[g]]);sum2[w] += del;ans += 2 * sum1[w] * del;}return 0;
}