N = 700 xs = range(1, N + 1) head = [0] * (N + 1) cur = 1 for i in range(N): cur *= xs[i] head[i] = cur head[-1] = 1 tail = [0] * (N + 1) cur = 1 for i in range(N - 1, -1, -1): cur *= xs[i] tail[i] = cur tail[-1] = 1 one_out_product = [head[i - 1] * tail[i + 1] for i in range(N)] # print(head) # print(tail) # print(one_out_product) if not"TEST": bluteforce = [1] * N for i in range(N): for j in range(N): if i == j: continue bluteforce[i] *= xs[j] #print(bluteforce) assert bluteforce == one_out_product

def solve(N, M, edges): # convert bidirectional graph to tree root = 1 parent = [-1] * (N + 1) to_visit = deque([root]) bfs_visited_order = [] while to_visit: cur = to_visit.popleft() bfs_visited_order.append(cur) for child in edges[cur]: if child == parent[cur]: continue parent[child] = cur edges[child].remove(cur) # remove back-link to_visit.append(child) # up-edge: v -> parent[v] # default: if no child, one black, one white (1 + 1) # f(x) = prod(f(c) for c in children) + 1 upedge = [0] * (N + 1) # stores multiply result (1 is unity) multiply_of_upedge = [1] * (N + 1) for cur in reversed(bfs_visited_order[1:]): # visit vertexes except root, in reversed order upedge[cur] = multiply_of_upedge[cur] + 1 p = parent[cur] multiply_of_upedge[p] *= upedge[cur] multiply_of_upedge[p] %= M # root: multiply children and don't add one # the one is "all-white" pattern upedge[root] = multiply_of_upedge[root] final_result = upedge[:] # down-edge: parent[v] -> v downedge = [1] * (N + 1) for cur in bfs_visited_order: prod = 1 # left-to-right accumlated products (* downedge[cur]) for child in edges[cur]: downedge[child] = prod prod *= upedge[child] prod %= M # multiply right-to-left accumlated products prod = 1 for child in reversed(edges[cur]): downedge[child] = (downedge[cur] * downedge[child] * prod) % M + 1 prod *= upedge[child] prod %= M for child in edges[cur]: # update final result final_result[child] = ( multiply_of_upedge[child] * downedge[child]) % M return final_result[1:]