P9437

首先这是一道很明显的换根 dp。 首先注意到要拼接数，所以我们可以先处理出 $num_i=10^{x}$，使得 $10^x > a_i > 10^{x-1}$，这样方便我们后面算贡献。 我们以这棵树为例子来推状态转移方程。 ![](https://cdn.luogu.com.cn/upload/im ......

赛时一眼换根 dp，然后调调调了大概 1h+。 [题目传送门](https://www.luogu.com.cn/problem/P9437) ### 什么是换根 dp 在大多数树形 dp 中，我们只考虑对根的贡献，而一部分题目需要算出对所有点的贡献，一个比较显然的做法是对每个点都跑一次树形 dp， ......

换根 DP。 本蒟蒻最初没想到换根，把自己写自闭了... 定义 $f_u$ 为子树 $u$ 中的每个结点走到 $u$ 的贡献和，$l_u$ 为大于 $a_u$ 的最小的 $10$ 的幂次方数，$sum_u$ 为 $\sum\limits_{v\in son(u)}{f_v}$。 转移方程为：$f_u ......