给定一棵大小为 \(n\) 的树，问能选出多少个非空的点集 \(S\)，使得若 \(u, v \in S\)，则 \(\text{LCA(u, v)} \in S\)。
\(T\) 次查询，每次给定 \(u\)，问假设删除 \(u\) 的子树后的答案是多少？
\(n, T \le 5 \times 10^5\)。
先不考虑 \(T\) 组询问。这个很树形 DP，设 \(dp_u\) 表示对于 \(u\) 的子树，答案是多少。下面设 \(v \in son_u\)。
- 若不选 \(u\)，只能从一个儿子继承：\(dp_v \rightarrow dp_u\)。
- 若选 \(u\)，则每个子树都没有限制：\(\prod (dp_v + 1) \rightarrow dp_u\)（\(+1\) 是加上空集。）
所以 \(dp_u = \sum dp_v + \prod(dp_v + 1)\)。
考虑查询，实际只需要对于每个 \(u\) 都算出答案即可。具体地，算出 \(dp_u\) 对于答案（\(dp_1\)）的贡献系数 \(f_u\) 即可。设 \(bro\) 为 \(u\) 的兄弟
\[dp_{fa_u} = \sum\limits dp_{bro} + (\prod(dp_{bro} + 1) + 1)dp_{u}
\]
根据这个，\(dp_u\) 对 \(dp_{fa_u}\) 的贡献系数为 \((\prod(dp_{bro} + 1) + 1)\)，\(dp_{fa_u}\) 对答案的贡献习俗为 \(f_{fa_u}\)，所以 \(f_u = f_{fa_u}(\prod(dp_{bro} + 1) + 1)\)。搞个前后缀积即可。
查询的答案为 \(dp_1 - f_u \dot dp_u\)。
时间复杂度：\(O(n)\)。
其实设计出 \(dp_u\) 不难，主要是询问。因为是一个加乘的形式，可以想到求出每个 \(dp_u\) 对答案的贡献有多少，从 \(fa_u\) 递推即可。