web analytics

有向无环图 DAG上的统计问题

路径统计就是个幌子,如果真正的去思考怎么统计路径,你就凉了

题目:https://ac.nowcoder.com/acm/contest/1112/B

题目的式子很吓人\(\sum_{i=1}^{n}\sum_{j=1}^{n}  count(i,j) * a_i * b_j \)

以后遇到DAG题的时候就应该想到,这个路径统计其实就是变相的告诉你后面的项会对前面的项产生影响,其实就是一种迭代的过程,所以我们的关注点应该在后面的\(a_i*b_j\)上

先考虑一个简单的链x->y->z我们会有式子\(a_x*b_y+a_x*b_z+a_y*b_z\)我们合并一下就会发现\(a_x*b_y + ( a_x + a_y ) * b_y\)所以我们在处理y的时候就可以统计,y之前的所有点的a的和,之后y的b再与这个和相乘。所以我们就可以用BFS来处理,先让入度为0的边进队,然后再拓展下面的边,处理一个去一个度,然后再将入度为0的边进队。每次b乘的时候就可以统计答案。