题目传送门明显的换根dp，感觉是道不错的换根dp练习题。题意一棵\(n\)个节点的树，点带权，定义\(w(x,y)=\overline{a_x\dotsa_y}\)。求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}w(i,j)\bmod998244353\)。思路我们不妨先求出\(i=1\)时的\(\sumw(i,j)\)，再求\(

P9437『XYGOIround1』一棵树trick+换根dp对于此类「将数字顺次写下」计算贡献的题目，通常按位考虑，并且考虑每个数作为开头/结尾时的贡献，方便计算。因此，我们在这题中考虑每个数作为结尾时的贡献。那么这题就转化成：计算以\(u\)为根并且以\(a_u\)为结尾的贡献。明显的换

首先这是一道很明显的换根dp。首先注意到要拼接数，所以我们可以先处理出\(num_i=10^{x}\)，使得\(10^x>a_i>10^{x-1}\)，这样方便我们后面算贡献。我们以这棵树为例子来推状态转移方程。先假设\(dp_u\)表示以\(1\)为根时，从\(u\)的子树的点到\(u\)的权值和。那么\[

赛时一眼换根dp，然后调调调了大概1h+。题目传送门什么是换根dp在大多数树形dp中，我们只考虑对根的贡献，而一部分题目需要算出对所有点的贡献，一个比较显然的做法是对每个点都跑一次树形dp，但是大大增加了时间复杂度，是我们不能接受的。树形dp中的换根dp问题又被称为二次扫

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