I recently found this question -

You have a tree of N nodes, and you can do M queries on the tree. The queries are of two types-

1 a x — add a to node x and all its descendents

2 x — find the sum of values of all nodes in the path b/w the root node and the node x (both root and x inclusive).

My brute-force approach — O(N*M)

Made a parent array for parent of each node, and a child vector of sets for children of each node. Also take an upd[n] and val[n] array to keep current pending update and value for each node.

For query 1 (update), just do upd[x] := upd[x] + a

For query 2 (sum from x to root), go backwards from x to root (using parent array), sum all the values along the way, apply val[i] := val[i]+upd[i] (i is b/w root and x) and update upd[y], where y is child of i.

http://ideone.com/IWDHtp

And as expected, it gives TLE for some test cases.

What is a faster approach for this? I am unable to come up with anything that updates and queries in less time.

Here is the link — http://mirror.codeforces.com/problemset/problem/559/C This is similar to this — https://www.codechef.com/CDCRF15R/problems/CWAYS/

In the solutions, I can see inverse factorial being calculated as

inv(n) = pow(n,mod-2)

I don't get where the mod-2 value comes from. Can someone please explain?

I read Cormen and Wikipedia pages for Max flow algorithms, but I feel that I'm very confused right now.

In my understanding, a max flow would basically work as follows:

1. Find an augmenting path and maintain a parent array. Should be O(E) using BFS.
2. Update the flow on all the edges on this path using the parent array. O(V) worst case. Update the max flow value.
3. Repeat the above steps until no more augmenting paths are found and return the max flow.

My questions are:

Ql. What is the limit on the number of times step 1 (bfs) is required?

Q2. Is this Edmond Karp or Dinitz algorithm that I'm talking about?

This is my first post, so I hope you will point out any problems in the way I've framed this question. Thanks.