求代码

小T有一颗n个节点的树。q次询问，每次给定两个点x,y,保证x不等于y，你需要求出有多少四元组（a,b,c,d）满足a,b之间的简单路径与c,d之间的简单路径交际恰好为x,y之间的简单路径。答案对998244353取模。

解题思路：若 x,y之间不存在祖先后代关系，那么直接考虑从 x 所在的子树和 y 所在的子树中选出两个点，使得它们的lca 分别是 x,y。 这实际上就直接是子树大小平方减去所有孩子的子树大小平方，预处理一下即可。若 x是 y 的祖先，那么情形是类似的，只不过 x点的子树要改为去掉那个包含y 的儿子的子树。方案数也可以直接通过上面的预处理 O(1) 得到。 包含 y 的儿子可以用倍增或树剖求出。 注意有序会带来 × 4 的贡献。 时间复杂度 O((n + m)log n )。