\(\text{heart}\)

\(\text{Solution}\)

可以记 \(f(u)\) 为从 \(u\) 出发到某个点停止的方案数，\(f(u)\) 可以 \(O(n)\) 转移，显然复杂度为 \(O(n^2)\).
当前我们要转移 \(u\) 子树内，对于 \(v\in \text{subtree(u)}\) 我们记 \(g_v\) 为 \(\min\limits_{p_k>p_j}p_k\)，其中 \(k\) 在 \(u\) 到 \(v\) 路径（不包含 \(u,v\)）上的节点，仅当 \(p_u<g_v\) 且 \(p_u>p_v\) 时 \(v\) 可以对 \(u\) 贡献，我们可以用线段树维护 \(f(u)\)，考虑线段树下标为 \(i\) 的位置维护 \(p_j=i\) 的 \(v_i=g_j\) 和 \(s_i=f(j)\)，我们可以先用对子树进行线段树合并然后考虑修改和查询

对于 \(k\in[1,p_i]\) 修改 \(v_k\leftarrow \min(v_k,p_i)\).
查询 \(\sum_{k=1}^{p_i}[v_k>p_i]s_k\).

可以用 \(\text{Segment Tree Beats}\) 维护，复杂度 \(O(n\log n)\).

\(\text{「USACO23OPEN」Triples of Cows P}\)

\(\text{Link}\)

发现删点后连边操作是 \(O(n^2)\) 级别的，考虑建虚点来优化。

具体的，考虑我们将原树上点称为黑点，新建的虚点为白点，我们将边拆为一个点，我们将原树上的边 \((u_i,v_i)\) 变为 \((u_i,n+i),(v_i,n+i)\)，由于 \(n\) 最后删去，我们可以以 \(n\) 为根。我们删点可以直接将所有儿子合并到父亲上，用并查集维护时间复杂度就是 \(O(n\log n)\) 的而且保证了图仍然是一棵树，原树 \(u,v\) 直接相连等价于黑点 \(u\) 和黑点 \(v\) 同时是某个白点的邻接点，我们用 \(\mathcal W\) 表示白点集合，用 \(\mathcal B\) 表示黑点集合。

考虑如何算贡献，考虑计算五元组 \((a,x,b,y,c)\)，其中 \(a,b,c\in \mathcal B,x,y\in \mathcal W\)，我们可以记录 \(f_u,g_u,h_u\) 为 \(u\) 的 \(1/2/3\) 级儿子数量。