一个不知道有啥意义的图。
CF1923E Count Paths
\(O(n^2)\)解法
设 \(dp_{u,i}\) 表示 \(u\) 的子树内一个颜色为 \(i\) 的点到 \(u\) 的链且路径上没有其他颜色为 \(i\) 的链数量。
如何状态转移？当点 \(u\) 加入一个儿子 \(v\) 时，把 \(v\) 中的链和 \(u\) 拼起来，此时 \(ans+=dp [v,c[u]]\)，加入是把其与 \(u\) 中另一条链拼起来，此时 \(ans+=dp[u,x] \times dp[v,x]\)，然后需要让 \(dp[u,x]\) 增加 \(dp[v,x]\) 也就是把链算入 \(u\) 的子树贡献中。
正解
注意到将 \(dp[v,x]\) 合并到 \(dp[u,x]\) 上复杂度较高。注意到由于两个状态只要一个为空就不产生变化，因此一个点 \(v\) 的状态数至多为 \(v\) 的子树大小。那么我们使用if else书上启发式合并，每次将小的状态暴力插入大的状态中并更新贡献，并用 map 维护一个点的所有状态。
复杂度是多少呢？每个点至多被插入 \(\log{n}\) 次，加上 map 的 \(\log{n}\) 就是 \(O(n \log^2{n})\)。
注意以下几个易错点:
- 整个过程中因为链一定经过了点 \(u\) 所以 \(dp[u,col[u]]\) 始终需要为 0。
- 算完所有贡献之后再算从点 \(u\) 自己开始的链，也就是让 \(dp[u,c[u]]\) 为 1。
代码没调出来TwT，写的另一种代码好些的写法。
另一种解法
注意到每种颜色是独立的。这里指的是无论两个颜色相同的节点之间是什么颜色，都不会干扰到后面的统计答案。可以直接把每种颜色分开算，但效率低下，我的做法就是一次dfs统计完答案。
设 \(cnt[a]\) 表示当前 \(a\) 这种颜色出现并且可以与之合法匹配的节点的个数，然后对整棵树进行dfs。流程如下：
-
一、在搜索到点 \(u\) 时，答案加上 \(cnt[c[u]]\)。
-
二、在进入以 \(u\) 为根的子树时，把 \(cnt[c[u]]\) 设为 1。因为路径上不能有其他点的颜色和起点终点相同，所以 \(u\) 的子孙不可能经过 \(u\) 与 \(u\) 的祖先和其他节点匹配，只能与 \(u\) 匹配。只能贡献 1 种方案。
-
三、在遍历完 \(u\) 的所有子树后，把 \(cnt[c[u]]\) 的值设为其在遍历子树前的值加 1。 因为如果令根节点为 \(u\)，按顺序考虑 \(u\) 的子树，每棵子树只有顶部的点（上面没有颜色与之相同的点）到现在的点的路径是合法的，子树与子树之间也是只有顶部的点合法，加 1 就表示加上 \(u\) 这个顶部的点。
每种方案恰好被计算一次。dfs 时间复杂度 \(O(n)\)。