【山东省选集训 2023】T1. 树染色
有多少种选出 \(\{(u_1,v_1),(u_2,v_2),...,(u_m,v_m)\}\) 的方法，使得：
- 任意 \(u_i\) 是 \(v_i\) 祖先；
- \(u_1=1\)；对于任意 \(i\ge 2\)，存在 \(j<i\) 使得 \(u_i\) 在 \(u_i\to v_i\) 的路径上；
- 所有边被至少一条路径 \(u_i\to v_i\) 覆盖。
对每组 \((u_i,v_i)\) 指定黑或白的颜色，按照 \(i\) 从小到大考虑每对 \((u,v)\)，若一条边第一次被染成黑则其价值为 \(a_i\)，否则其价值为 \(b_i\)。对于一种染色方式，其价值定义为所有边的价值积。求所有方案（选 \(m\) 个二元组 + 指定颜色）的价值和。
\(n\le 5\times 10^5\)。