无根树。多次询问：给定简单路径，求树上有多少个连通子图与这路径至少有一个公共点。

Idea

树上连通子图问题找连通子图的深度最低点。

Solution

设

• $f_u$（题解里的 $dp(u, 0)$）：以 $u$ 为根的子树内，包含节点 $u$ 的连通子图数量。转移：$\displaystyle f_u = \prod_{v \in \text{children}(u)} (f_v + 1)$。
• $g_u$（题解里的 $dp(u, 1)$）：包含 $u$ 的父节点，不含 $u$ 的子树的连通子图数量，特别地，对于根节点 $r$，$g_{r} = 0$。转移：$\displaystyle g_u = (g_{\operatorname{parent}(u)} + 1) \prod_{c \in \text{sibling}(u)} (f_c+1)$。

那么 $$ \boxed{\text{Answer} = f_{\operatorname{lca}(x,y)}\cdot g_{\operatorname{lca}(x,y)}+\sum_{z\in \operatorname{path}(x,y)}f_{z}} $$ 预处理前缀和、LCA 后可直接计算。

Proof

考虑任何一个与路径 $\operatorname{path}(x,y)$ 相交的连通子图 $C$。在 $C$ 与路径 $\operatorname{path}(x,y)$ 的所有公共节点中，找到深度最低的节点，记为 $z$。

• 如果 $z=\operatorname{lca}(x,y)$，那么所有包含 $\operatorname{lca}(x,y)$ 的连通子图 $C$ 都合法，方案数包含某点的连通子图计数，即 $f_{\operatorname{lca}(x,y)}\cdot (g_{\operatorname{lca}(x,y)}+1)$。
• 否则，意味着连通子图 $C$ 包含节点 $z$，但不包含 $z$ 在路径 $\operatorname{path}(x,y)$ 上的父节点 $\operatorname{parent}(z)$，此时的方案数就是 $f_{z}$。这里 $z$ 需要取遍 $\operatorname{path}(x,y)$ 上的点，除去 $\operatorname{lca}(x,y)$。

两种情形相加即可。