题解

题目类型：树形 DP（长链剖分 / 小并大优化）
核心目标：在一棵无根树上统计某种与路径长度或节点深度有关的数量（常见为路径配对数、等距节点对数等）。
本题代码使用了 长链剖分（Long Chain Decomposition）+ 动态数组偏移合并 的优化技巧。

一、思路概述

整体框架为两次 DFS：

1. 第一次 DFS（dfs1）
   计算每个节点的深度 dep[u]、子树中最深节点深度 mx[u]，并找出它的 重儿子（深度最大的子节点）son[u]。

   • 目的：为第二次 DFS 分配连续内存空间和确定“长链”的继承关系。

2. 第二次 DFS（dfs2）
   进行树形 DP：

   • f[u][d]：以 u 为根的子树中，到深度差为 d 的节点数。
   • g[u][d]：以 u 为根的子树中，经过 u、路径长度为 d 的路径对数。

   通过“长链继承 + 轻儿子合并”的方式，在一次 DFS 中求出全树的统计量。

二、状态定义与转移

1️⃣ 定义

• f[u][d]：距离 u 为 d 的节点个数。
  即从 u 出发往下走 d 条边可达的节点数。
  （f[u][0] = 1 表示自己）

• g[u][d]：以 u 为最高点、长度为 d 的路径对数。
  （g[u][0] 表示经过 u 的长度为 0 的路径，即空路径）

2️⃣ 重儿子继承

为了避免重复分配数组空间，我们让重儿子的 f[son[u]] 与 g[son[u]] 直接指向父亲数组的偏移部分：

f[son[u]] = f[u] + 1;
g[son[u]] = g[u] - 1;

这样父子间数据连续分布，形成“长链继承”结构，可在 O(n) 空间下保存所有层次信息。

3️⃣ 转移过程

对每个轻儿子 i：

1. 分配独立的内存区：

   f[i] = id; id += mx[i] << 1;
   g[i] = id; id += mx[i] << 1;
   

   （<<1 相当于乘 2，预留正负下标空间）

2. DFS 处理轻儿子：

   dfs2(i, u);
   

3. 合并贡献：

   ans += g[i][1];  // 子树 i 中距离 1 的路径
   for (int j=1;j<=mx[i];j++)
       ans += g[u][j]*f[i][j-1] + f[u][j]*g[i][j+1];
   

   • g[u][j]*f[i][j-1]：经过父节点 u、一端在主链、另一端在子树 i 的路径；
   • f[u][j]*g[i][j+1]：另一种对称情况；
   • 循环中不断更新 ans。

4. 合并 f、g：

   for (int j=0;j<mx[i];j++) g[u][j] += g[i][j+1];
   for (int j=1;j<=mx[i];j++) g[u][j] += f[u][j]*f[i][j-1];
   for (int j=1;j<=mx[i];j++) f[u][j] += f[i][j-1];
   

   相当于：

   • 子树 i 的路径对贡献到父节点；
   • 把节点数统计向上累加。

三、优化思想：长链剖分 + 指针偏移

传统“树形 DP 合并子树”复杂度为 (O(n^2))，因为每次都需要新开数组并做卷积合并。

这里通过 长链剖分 + 数组指针共享 技术，将复杂度优化为近似 O(n)：

• 对每个节点只给轻儿子分配独立数组；
• 重儿子沿用父节点的偏移数组；
• 合并时仅线性扫描一遍深度范围，无需多次拷贝。

四、执行流程

1. DFS1

   • 确定每个点的深度与最大深度；
   • 记录重儿子。

2. DFS2

   • 递归重儿子，继承父节点偏移；
   • 对每个轻儿子：
     • 分配独立空间；
     • 计算；
     • 把结果累加进父节点；
   • 统计全局答案。

最终输出 ans。

五、复杂度分析

六、代码实现（与题给一致）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,ans=0,dep[100005],mx[100005],son[100005];
int *f[100005],*g[100005],tmp[400005],*id=tmp;
vector<int> v[100005];
void dfs(int u,int f){
    dep[u]=dep[f]+1,mx[u]=dep[u];
    for(int i:v[u]){
        if(i==f)continue;
        dfs(i,u);if(mx[son[u]]<mx[i])son[u]=i;
    }
    mx[u]=mx[son[u]]+1;
}
void dfs2(int u,int fa){
    if(son[u])f[son[u]]=f[u]+1,g[son[u]]=g[u]-1,dfs2(son[u],u);
    f[u][0]=1;ans+=g[u][0];
    for(int i:v[u]){
        if(i==fa||i==son[u])continue;
        f[i]=id,id+=mx[i]<<1,g[i]=id,id+=mx[i]<<1;
        dfs2(i,u),ans+=g[i][1];
        for(int j=1;j<=mx[i];j++)ans+=g[u][j]*f[i][j-1]+f[u][j]*g[i][j+1];
        for(int j=0;j<mx[i];j++)g[u][j]+=g[i][j+1];
        for(int j=1;j<=mx[i];j++)g[u][j]+=f[u][j]*f[i][j-1];
        for(int j=1;j<=mx[i];j++)f[u][j]+=f[i][j-1];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
    dfs(1,0),f[1]=id,id+=mx[1]<<1,g[1]=id,id+=mx[1]<<1;
    dfs2(1,0),cout<<ans;
    return 0;
}

✅ 总结

• 本题是树形 DP 的经典“长链剖分 + 数组偏移共享”技巧示例；
• 通过 f/g 两组 DP 状态统计路径对；
• 使用指针偏移代替多重嵌套卷积，极大优化效率；
• 模板结构可用于任意“按深度合并子树”的问题。