题意
做法
第一次打uoj比赛,居然有签到题,体验良好qwq
容易观察到,一个点一旦加入(S)就不会再出来,且边形成了一个虚树。
任意时刻,操作为在虚树中的某条边中间选取一个点加进来,或在外面选取一个点,与虚树的一个叶子连边。
自然的,会想到对于一棵树,目前(S={root}),枚举一个点(x),那么路径( ext{root-x})中间的点可以随意选取顺序:假设中间除(x,root)有(m)个点,这部分复杂度为(m!)。
断开这些边,对于剩下若干棵树,即可转化为子问题。
有本质不同(O(n))个子问题,这样能做到(O(n^3))或(O(n^2))。
这题性质非常好:对于根节点(root),假设其有若干子树,那么若干子树都是分别独立的。
那么令(f_i)为单独考虑(i)子树,初始(S={i})的方案数。
递归解决这个问题,但现在,通过(root)的若干儿子的(f_i)直接得到(f_{root})是无法做到的,因为儿子进入这个集合的时间未知。
额外的,令(g_i):在(i)子树的基础上,(i)上面加入一个点(即钦定(i)有父亲节点),(S)初始为(fa_i),的方案数。
因为如果我们得到了(g_i),那么可以通过(root)儿子节点的(g_{v_i}),很容易得到(f_{root})。
考虑得到(g_u),两种情况
(1)(fa_u)第一次就选取了(u),此时方案数为(f_u)
(2)(fa_{u})一开始延伸到了(u)的某个子树,这种情况较为复杂。
假设(u)的儿子分别为({v_1,ldots,v_m}),令(size_i)为(i)子树大小。
当(S)延伸到了(v_i),在(S)子树加入(u)前,(S)不会延伸到其他子树,而且在加入(u)后,(u)的儿子就相互独立了,枚举(u)加入的时间:
最后那个和式,是经典组合数上指标求和,很容易得到封闭形式。
总复杂度(O(n))。