Source - 区模拟赛
Description
EZ 同学家里非常富有，但又极其的谦虚，说话又好听，是个不可多得的人才。
EZ 常常在假期环游世界，他准备去 N（ N<=100000）个国家之多，一些国家有航线连接，由于 EZ 同学有一定的强迫症，任意两个国家之间都能通过航路直接或间接到达，并且这样的路径仅有一种。（简单来说，这些国家构成了一棵树）
由于 EZ 是 C 国人，因此将 C 国（ 1 号国家）作为整棵树的根
每个国家有一个旅游热度 A[i]和影响力 D[i]。由于目的地有点多，为了避免选择困难症，他给每个国家设置了一个向往值 F[i]， 它等于所有的 A[j]之和，满足 i 国在 j 国向 C 国走 D[j]步的路径上（经过一条航路算一步， i=j 也会被统计，如果 D[j]步超过了 C 国，则超出部分不用管）。
LYD 同学家里有矿，富有程度与 EZ 不相上下，但他却在宅与现充间摇摆不定。某次机缘巧合， EZ 外出旅游刺激了 LYD，他决定也要开始旅游。为了避免又被判高重复率导致被取消资格，他将 EZ 的旅游地图略微做了一点调整， 每条航路将有一定的概率出现。
现在他有 Q 个询问，每次询问某个国家所在的联通块（由于每条边是一定概率出现，因此它所在的联通块可以是很多种）中所有国家的 F[i]值的和的平方的期望（对 998244353取模）， 以此来决定他旅游的目的地。但他极其厌恶繁琐的计算，于是他找到了能算出圆周率并将它倒背下来的你，答应给你丰厚的报酬。家里没矿，老爸也不是 X 达集团老总的你决定接受他的任务。
Input
第一行 1 个正整数 N，表示国家数。
接下来 N 行，第 i 行两个非负整数 A[i],D[i]，表示国家 i 的旅游热度以及影响力
接下来 N-1 行，每行三个非负整数 x,y,v， x,y 为这条航路连接的两个国家， v 为这条航路出现的概率。（注意每个在 EZ 的地图中是没有出现概率的说法的，因此每个国家的 F 值与边的出现概率无关）
接下来一行一个正整数 Q，表示询问数
接下来 Q 行，每行一个正整数 x，表示询问国家 x 所在的联通块中所有国家的 F[i]值的和的平方的期望（对 998244353 取模）。
Output
Q 行，每行一个非负整数表示这次询问的答案。
Solutions
吐槽一下。考试时候，我直接当作线性关系来合并样本空间，然后疯狂WA样例。在手算样例后，才发现似乎不满足线性关系…等我发现这个结论，并且改过样例的时候，我已经在这题上消耗2h了….这还是我第一次遇到要从期望定义出发去解决合并样本空间的问题(暴露了做题少的本质)…
先处理下$F_i$。对每个节点分别考虑。对于节点$i$，能够对$i$的第$D_i$个祖先到$i$的路径上产生$A_i$的贡献。因此直接树上差分后即可求得每个$F_i$，时间复杂度$O(n)$。
接着考虑如何求期望。如果询问的总是根节点的话，那么容易将问题转换成求各个子树的期望。但询问不一定是根节点，因此对于每个节点需要分别维护子树期望以及非子树期望。
问题的关键在于合并信息。我们从定义出发，假设合并的两个样本空间分别为$A,B$，连接两个样本空间的边的概率为$P$。那么题目所求期望为
化简一下有
$\sum_i p_i a_i^2, \, \sum_j p_j b_j^2$显然是样本空间$A,B$的$F_i$和平分的期望，而$(\sum_i p_ia_i)(\sum_j p_j b_j)$则是样本空间$A,B$的$F_i$和的期望。因此只需要维护和的期望、和平分的期望就能够处理合并。
时间复杂度$O(n)$。
CODE
CODE - Click Here