\(\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\) 级儿子数量。
- \(x=y\)，我们可以在 \(x\) 的邻接点中任选 \(3\) 个互不相同的点即可，贡献为
- \(x\not= y\)，我们可以枚举 \(b\) 然后分为两种情况讨论