考虑 Prüfer 序列构造树的过程，从前往后扫过整个序列，记录当前度数为 1 的点集 S，以及已经被删除的点集 T，每次如果遇到数 x\not\in (S\cup T)，那么就将 S 中最小值连上 x，然后删除 S 中的最小值将其加入 T，而 x 则可能可以加入 S 也可能不加入 S，序列扫完后必然 |S|=1,|T|=n-2，这时 S 中唯一的数就会连上 n。
于是可以如此 dp，设 f(i,j,S,T) 表示考虑 i\sim m 这个序列中的子序列为最后一段，S,T 为上面描述的两个点集，其中 j 与 n 距离的总和以及方案数。按照上面转移 O(1)，且 S\cap T=\varnothing，所以复杂度为 O(3^nnm)。
考虑 Prüfer 序列具体构造过程是如何从 O(n\log n) 优化到 O(n) 的，类似的，优化掉 3^n，用一个集合 L=S\cup T，那么实际上 S 就是 L 的一个后缀加上最多前面一个新加的点，所以可以将 3^n 优化到 2^nn^2，时间复杂度复杂度优化为 O(2^nn^3m)。
但是我们发现如果当且 dp 要求的是 j 与 n 的距离，那么我们唯一关心的就是 j 连出去的父亲，所以如果新加的点如果不是 j 那么我们其实完全不关心它具体是谁，于是一个 n 可以被优化为一个 01 储存的状态，即 S 中当前最小的点是否恰好为 j，于是时间复杂度优化为 O(2^nn^2m)，可以通过所有数据。