DP V

Given a tree, the problem of finding the total number of fillings that can be reached from any black vertex to any black vertex through only black vertices

Am I understanding that you want the number of subtrees?

Oh, you want to answer "how many combinations such that vertex v is black? Simply asking for a subtree would increase the order by a factor of N, so you want to use a subproblem.

RE only where the problem is big enough to make it rustic.

I thought a dictionary with tuples as keys would be slower, so I used product integers as indexes.

N goes up to 10^5, so the square is 10^10 and MemoryError

There's a lot of memory on hand, so it works.

It was hard to find the cause of the problem because it would be RE instead of MLE.

The tally becomes O(N) when there are many edges growing from one vertex.

Aggregation of a lot of things removed from a lot of things" requires using the result of an operation to reduce the amount of calculation.

Aggregation by multiplication cannot do "one back from all multiplied by one" because there is no inverse original to zero, while addition can do it because there is an inverse original....

So make the cumulative product from the front and from the back

I think this is always necessary with a graph that has no rank limit.

code:python

N = 700

xs = range(1, N + 1)

cur = 1

for i in range(N):

cur = 1

for i in range(N - 1, -1, -1):

# print(head)

# print(tail)

# print(one_out_product)

if not"TEST":

for i in range(N):

for j in range(N):

if i == j:

continue

assert bluteforce == one_out_product

You've made it, but when is the right time to execute this?

Read other people's code

Python 523msec

I see, my code is divided into three categories "all white, black roots, and otherwise white roots" and propagates the latter two, but if the child's roots are white, the parent cannot be black, so it is always ignored in the final calculation, so there is no need to propagate it.

Just an update to "multiply by the value of the child and add 1."

Adding one is a pattern where the child is all white.

Moreover, recursive calls are not necessary, and First, it records the order traced by the width-first search. Also, at that time, the opposite edges are erased.

https://gyazo.com/b910e1af8eb9355d9717ec6f26604f7f

code:python

def solve(N, M, edges):

# convert bidirectional graph to tree

root = 1

bfs_visited_order = []

while to_visit:

cur = to_visit.popleft()

bfs_visited_order.append(cur)

continue

to_visit.append(child)

# default: if no child, one black, one white (1 + 1)

# f(x) = prod(f(c) for c in children) + 1

# stores multiply result (1 is unity)

# visit vertexes except root, in reversed order

# root: multiply children and don't add one

# the one is "all-white" pattern

for cur in bfs_visited_order:

prod = 1

prod %= M

# multiply right-to-left accumlated products

prod = 1

prod %= M

# update final result

---