我很久以前就做过这道题，但是当时没有想出来于是扔掉了（在状压dp那块），今天被学长重新拿出来再讲一次，终于有了点思路。
先讲一下暴力思路，说是暴力也很难想了。设dp[i][j][s]为以树上编号为i的点为子树，i对应原图的j的，s是i的子树中包含对应原图中的点状态为s的方案数。
那么写一下式子。
$ dp[i][j][s]= sum limits_t^{t|s=phi} sum limits_{v,v otin s}^{e(j,v)} sum limits_t^{tin{son[i]}}dp[t][v][t] $
也就是说枚举s的补集和与j相连的v以及i的儿子t来进行转移，
时间复杂度是 $ O(3^n n^2) $ 会炸掉。
关于补集的复杂度是$ 3^n $ 的证明。
证明：
设枚举的子集中的元素个数是i，那么这种子集的个数就是$ 2^i $。
那么：
$ ans=sum limits_{i=0}^n C_n^k 2^i $
$ =sum limits_{i=0}^n C_n^k 2^i 1^n-i $
由二项式定理得:
$ ans=(2+1)^n=3^n $
证毕。
现在考虑正解，如果我们删去最后一维会怎么样。
我们无法统计到底是否是一个双全集映射，因为可能有许多点没有被计算入最终的情况，也就是所谓重复的图点出现在树中，虽然连接是合法的，但是集合映射不同。
考虑大力容斥。
我们用每个点都在映射范围内的减去有一个不在的，再加上有两个在的，在减去……
奇加偶减，容斥出结果。