题意
链接：https://www.codechef.com/problems/MAXDTREE
给定一个 \(n\) 个节点的树，其中 \(1\) 为根节点，每个点有点权，我们定义“子树”为若干条到根的链的并。给定一个无穷数列 \(\{a_n\}\) ，其构造方法如下：
\[a_n=\begin{cases}
1& n=1\\
a_{n-1}+\text{maxDigit}(a_{n-1})&n>1
\end{cases}
\]
其中 \(\text{maxDigit}(n)\) 函数为 \(n\) 的最大数位。
这个无穷数列的前 \(6\) 项为 \(1,2,4,8,16,22\cdots\) ，求原树有多少个子树先序遍历得到的权值序列包含在 \(\{a_n\}\) 中。
\(\displaystyle\sum n\leq 500\)
思路
先考虑如何 \(O(n)\) 判断一个数列在不在 \(\{a_n\}\) 中出现过。
考虑从高位到低位一位一位的填数，我们把填数的状态记作一个 \(xxx00000a\) 形式的数，那么存有几个 \(0\)，高位的最大值是多少足矣，这些状态显然是足够表示所有情况的。我们为了转移，就需要一个四维的转移数组，对于一个状态 \(xxx0000a\) ，告诉这个数组最高位的 \(0\) 的位置 、\(xxx\) 中的最大值、个位数 \(a\)、要在最高的 \(0\) 填什么，这个数组就告诉你填完最高位 \(0\) 后（\(xxxx0000a\)），个位数 \(a\) 变成了多少。
接下来考虑怎么 \(\text{dp}\) 得到这个数组，考虑设 \(f[i][j][k]\) 为最高的 \(0\) 为 \(i\) ，\([2,+\infty)\) 的最大数位为 \(j\) ，个位为 \(k\) ，当第 \(i\) 位发生进位时，个位变成了多少，\(g[i][j][k][l]\) 为最高的 \(0\) 为 \(i\) ，\([2,+\infty)\) 的最大数位为 \(j\) ，个位为 \(k\) ，第 \(i\) 位刚刚变成 \(l\) 时，个位变成了多少。可以通过在 \(i-1\) 位不断用 \(f\) 数组进位得到 \(i\) 位的 \(f,g\) 数组，然后就可以转移了。\(g[1]\) 数组的值可以用 \(-1\) 代表这个状态个位达不到，由此判断无解。
上文提到的 \(O(n)\) 判断算法如下：
bool judge(int *num,int len)
{
int p=0,a=1;
DOR(i,len,2)
{
a=g[i][p][a][num[i]];
p=std::max(p,num[i]);
}
return g[1][p][a][num[1]]!=-1;
}
我们接下来考虑如何把这个过程存在 \(dp\) 数组里，在树上进行 \(\rm{dp}\) 。
事实上，上面的函数封闭性已经足够的好，以至于我们可以完全抛下之前 \(\rm{dp}\) 填数的过程，面向 \(\rm{judge}\) 函数进行所谓 \(\rm{dp}\) 套 \(\rm{dp}\) 的过程。
不难发现，按照题目“子树”的定义，当我们填了一个 \(u\) 节点，我们上一个填的节点编号可以为 \([{\rm{dfn}}_{fa_u},{\rm dfn}_u)\) ，以此，我们可以按顺序填数，定义 \(dp[i][j][k][l]\) 为在节点 \(i\) ，\(\rm{judge}\) 函数中的 \(i\) 为 \(j\) ，\(\rm{judge}\) 函数中的 \(p\) 为 \(k\) ，\(\rm{judge}\) 函数中的 \(a\) 为 \(l\) 的方案数，每次转移先枚举这个点，上个点，然后由上个点刷表到这个点。
细节有很多，最重要的是要 “划清内层 \(\rm{dp}\) 的循环过程“。比如我选取 \(\rm{judge}\) 函数的 \(4,5,6,7\) 行作为顺序，然后第 \(3\) 行也可以当成是 \(len+1\) 循环的结束，当然，这样就要在树上的根结点上再加一个特殊节点。
最后由于是个区间的转移，可以前缀和优化，然后就可以通过本题了。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=505;
const int P=1e9+7;
std::vector<int>G[N];
int f[N][12][12],g[N][12][12][12],dp[N][N][12][12],sdp[N][N][12][12];
int fa[N],lfn[N],ori[N],dfs_idx;
int d[N];
int n,K;
//xxxxx000000a
//f[i][j][k] [2,i]位为0，[i+1,+infty)的最大数位为j，个位为k，第i位进位后个位变成多少
//g[i][j][k][l][2,i]位为0，[i+1,+infty)的最大数位为j，个位为k，第i位变成l后个位变成多少
//dp[i][j][k][l] 在dfs序为i的节点，judge函数中的i为j，函数中的p为k，函数中的a为lvoid init()
{
FOR(i,0,K-1)FOR(j,0,K-1)if(i||j)
{
int a=j;
while(a<K)a+=std::max(i,a);
f[1][i][j]=a-K;
}
FOR(i,2,n)FOR(j,0,K-1)FOR(k,0,K-1)if(j||k)
{
int a=k;
FOR(l,0,K-1)
{
g[i][j][k][l]=a;
a=f[i-1][std::max(l,j)][a];
}
f[i][j][k]=a;
}
FOR(i,0,K-1)FOR(j,0,K-1)if(i||j)
{
FOR(k,0,K-1)g[1][i][j][k]=-1;
int a=j;
while(a<K)g[1][i][j][a]=a,a+=std::max(i,a);
}
}bool judge(int *num,int len)
{
int p=0,a=1;
DOR(i,len,2)
{
a=g[i][p][a][num[i]];
p=std::max(p,num[i]);
}
return g[1][p][a][num[1]]!=-1;
}void dfs(int u,int f)
{
fa[u]=f;
ori[lfn[u]=++dfs_idx]=u;
FOR(i,0,(int)G[u].size()-1)
{
int v=G[u][i];
if(v==fa[u])continue;
dfs(v,u);
}
}int main()
{
int T;
scanf("%d",&T);
while(T--)
{
K=10;
scanf("%d",&n);
init();/*FOR(i,1,100)
{
int num[4],len=0,x=i;
num[++len]=x%10,x/=10;while(x);
printf("i=%d judge(%d)=%d\n",i,i,judge(num,len));
}*/FOR(i,0,n)G[i].clear();
G[0].push_back(1);
G[1].push_back(0);
FOR(i,1,n-1)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
FOR(i,1,n)scanf("%d",&d[i]);
FOR(i,0,n)std::sort(G[i].begin(),G[i].end());dfs_idx=0;
dfs(0,-1);
FOR(i,0,n+1)FOR(j,2,n+1)FOR(k,0,K-1)FOR(l,0,K-1)sdp[i][j][k][l]=dp[i][j][k][l]=0;
FOR(i,2,n+1)sdp[1][i][0][1]=dp[1][i][0][1]=1;
int ans=0;
FOR(u,2,n+1)
{
int _u=ori[u];
FOR(i,2,n+1)FOR(j,0,K-1)FOR(k,0,K-1)
{
if(i==2)
{
if(g[1][j][k][d[_u]]!=-1)
{
/*FOR(v,lfn[fa[_u]],u-1)
(ans+=dp[v][i][j][k])%=P;*/
(ans+=(sdp[u-1][i][j][k]-sdp[lfn[fa[_u]]-1][i][j][k]+P)%P)%=P;
}
}
else
{
/*FOR(v,lfn[fa[_u]],u-1)
(dp[u][i-1][std::max(d[_u],j)][g[i-1][j][k][d[_u]]]+=dp[v][i][j][k])%=P;*/
(dp[u][i-1][std::max(d[_u],j)][g[i-1][j][k][d[_u]]]+=(sdp[u-1][i][j][k]-sdp[lfn[fa[_u]]-1][i][j][k]+P)%P)%=P;
}
}
FOR(i,2,n+1)FOR(j,0,K-1)FOR(k,0,K-1)
sdp[u][i][j][k]=(sdp[u-1][i][j][k]+dp[u][i][j][k])%P;
}
printf("%d\n",ans);
}
return 0;
}
