题意：

task0，给定两棵树T1，T2，取它们公共边(两端点相同)加入一张新的图，记新图连通块个数为x，求y^x。

task1，给定T1，求所有T2的task0之和。

task2，求所有T1的task1之和。

解：task0，显然按照题意模拟即可。

task1，对某个T2，设有k条边相同，那么连通块数就是n - k。要求的就是

对于每个T2，前面yⁿ都是一样的，所以直接去掉，最后乘上即可。关注后面这个东西怎么求。令y' = 1/y，E是公共边集。

注意到

这里下式是枚举边集E的子集S，对每个的子集贡献求和。

注意上式先枚举a再求组合数，相当于枚举在边集里选a条边，然后枚举选哪a条边。也就是枚举子集。

也就是下面这段话想表达的。摘自Cyhlnj。

容斥写法在下不会T_T

下一步，把S提前枚举，在不同的E中同一个S的贡献总是相同的。考虑一个S会对哪些E产生贡献，也就是它的贡献会被计算多少次。

这|S|条边会形成若干个连通块。这些连通块通过加上一些边可以形成树。这些新边没有任何限制，于是就是连通块的生成树计数。

这里又有若干种推法......个人认为最简单的是利用prufer序列求解。

摘自Joker_69。

令z = y' - 1，m = 边集为S时的连通块数 = n - |S|，第i号连通块有ai个点，于是我们的答案变成了这样：

这个东西怎么求呢？注意到在T1中选择任意的边集S等价于把T1划分为若干个连通块。于是就考虑树形DP。

这后面这个求积，要乘上每个连通块的大小，换个思路就是在每个连通块中选一个关键点的方案数。

于是状态设计有f[x][0/1]表示在以x为根的子树中，x所在连通块是否选择了关键的所有方案权值之和。

转移的时候考虑若x作为一个单独的连通块，那么每个子树都要是1。若x是其中某些连通块的延伸，再考虑关键点是在子树还是x还是子树外。