1 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define pb push_back #define vi vector<int> #define rd(x) scanf("%d", &x) #define print(x) printf("%lld\n", x) typedef long long ll; const int N = 1e5 + 7; int n, d[N], dep[N], son[N]; vi e[N]; ll *f[N], *g[N], p[N<<2], *o = p, ans; void dfs(int x, int fa) { d[x] = d[fa] + 1; for (auto y : e[x]) if (y != fa) { dfs(y, x); if (dep[y] > dep[son[x]]) son[x] = y; } dep[x] = dep[son[x]] + 1; } 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 (auto y : e[x]) if (y != fa && y != son[x]) { f[y] = o, o += dep[y] << 1, g[y] = o, o += dep[y] << 1; dp(y, x); for (int i = 0; i < dep[y]; i++) { if (i) ans += f[x][i-1] * g[y][i]; ans += g[x][i+1] * f[y][i]; } for (int i = 0; i < dep[y]; i++) { g[x][i+1] += f[x][i+1] * f[y][i]; if (i) g[x][i-1] += g[y][i]; f[x][i+1] += f[y][i]; } } } int main() { rd(n); for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x); dfs(1, 0), f[1] = o, o += dep[1] << 1, g[1] = o, o += dep[1] << 1; dp(1, 0), print(ans); return 0; }
- 1
信息
- ID
- 6208
- 时间
- 1000ms
- 内存
- 500MiB
- 难度
- 9
- 标签
- 递交数
- 11
- 已通过
- 3
- 上传者