长链剖分优化 \(dp\) 模板
不过这 \(dp\) 真毒
\(\text{Code}\)
#include <cstdio>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, h[N], tot, len[N], son[N];
struct edge{int to, nxt;}e[N << 1];
IN void add(int x, int y){e[++tot] = (edge){y, h[x]}, h[x] = tot;}
void dfs(int x, int fa)
{
for(RE int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa) continue;
dfs(v, x), son[x] = (len[v] > len[son[x]] ? v : son[x]);
}
len[x] = len[son[x]] + 1;
}
LL tmp[N << 2], *id = tmp, *f[N], *g[N], ans;
void DP(int x, int fa)
{
if (son[x]) f[son[x]] = f[x] + 1, g[son[x]] = g[x] - 1, DP(son[x], x);
f[x][0] = 1, ans += g[x][0];
for(RE int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa || v == son[x]) continue;
f[v] = id, id += len[v] << 1, g[v] = id, id += len[v] << 1, DP(v, x);
for(RE int j = 0; j < len[v]; j++)
{
if (j) ans += f[x][j - 1] * g[v][j];
ans += g[x][j + 1] * f[v][j];
}
for(RE int j = 0; j < len[v]; j++)
{
g[x][j + 1] += f[x][j + 1] * f[v][j];
if (j) g[x][j - 1] += g[v][j];
f[x][j + 1] += f[v][j];
}
}
}
int main()
{
scanf("%d", &n);
for(RE int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
dfs(1, 0), f[1] = id, id += len[1] << 1, g[1] = id, id += len[1] << 1, DP(1, 0);
printf("%lld\n", ans);
}