题面

解法

MLE了23333

~~为什么空间不给256MB，这样我就能开几个5000*5000的数组了~~

考虑一种树形dp的方法吧

\(f_{i,j}\)表示从点\(i\)向下走\(j\)步并选出两个不在\(i\)同一个子树的方案数，\(g_{i,j}\)表示从\(i\)出发在\(i\)子树外走\(j\)步的方案数

那么答案即为\(\sum f_{i,j}×g_{i,j}\)

注意统计时可能会出现重复的情况

时间复杂度：\(O(n^2)\)

当然，还有一种复杂度为\(O(n^2)\)的方法，直接枚举三个点的中心点，然后暴力dfs统计答案

感觉这个比较容易实现

代码

#include 
    
     #define N 5010using namespace std;template 
     
       void chkmax(node &x, node y) {x = max(x, y);}template 
      
        void chkmin(node &x, node y) {x = min(x, y);}template 
       
         void read(node &x) {    x = 0; int f = 1; char c = getchar();    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}struct Edge {    int next, num;} e[N * 3];int n, cnt, p[N], f[N][N], g[N][N], s[N][N];long long ans = 0;void add(int x, int y) {    e[++cnt] = (Edge) {e[x].next, y};    e[x].next = cnt;}void dpI(int x, int fa) {    s[x][0] = 1, p[x] = fa; int tot = 0;    for (int p = e[x].next; p; p = e[p].next) {        int k = e[p].num;        if (k == fa) continue;        dpI(k, x); tot++;        for (int i = 1; i <= n; i++) {            if (tot >= 3) ans += 1ll * f[x][i] * s[k][i - 1];            f[x][i] += s[x][i] * s[k][i - 1];            s[x][i] += s[k][i - 1];        }    }}void dfs(int x, int fa, int y, int sum) {    g[y][sum]++;    for (int p = e[x].next; p; p = e[p].next)        if (e[p].num != fa) dfs(e[p].num, x, y, sum + 1);}int main() {    read(n); cnt = n;    for (int i = 1; i < n; i++) {        int x, y; read(x), read(y);        add(x, y), add(y, x);    }    dpI(1, 0);    for (int i = 1; i <= n; i++)        for (int q = e[i].next; q; q = e[q].next)            if (e[q].num == p[i]) dfs(p[i], i, i, 1);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= n; j++)            ans += 1ll * f[i][j] * g[i][j];    cout << ans << "\n";    return 0;}