# cses - counting paths

Here is the problem statement: [link](https://cses.fi/problemset/task/1136)
You are given a tree consisting of n nodes, and m paths in the tree.
Your task is to calculate for each node the number of paths containing that node.

To solve this, we will need a few techniques. They are discussed below:

### Difference array technique

Lets say we are given an array of integers and we have queries of the form : `l r x` which means add x to all elements of array with indices in range `[l,r]`. We have several such queries, and after all queries, we wish to find the final array.

**Nieve approach:**
Perform the addition to all elements in the given range for all queries. Overall complexity: $O(nq)$

**Faster approach:**
Let us initially create an array `diff` of zeroes of size `n+2`. We assume that `l, r` are 1-indexed. Now for every query, we do the following: add `x` to `diff[l]` and subtract `x` from `diff[r+1]` (`diff` is 0-indexed). After all the queries are over, we take the prefix sum over `diff`, and what we get is finally the amout that needs to be added to the original array `a` to obtain the final array after all queries. Let us take an example:

`a = [3 5 1 1 6]`
queries:
`[1 2 1]`
`[3 5 2]`
`[5 5 5]`

`diff = [0 0 0 0 0 0 0]`
query 1:`[0 1 0 -1 0 0 0]`
query 2:`[0 1 0 1 0 0 -2]`
query 3:`[0 1 0 1 0 5 -7]`
prefix sum: `[0 1 1 2 2 7 0]`
final a: `[4 6 3 3 13]`

Let us see why this works:
Our aim was to reduce the costs per query, so we typically wanted the per query cost to be $O(1)$. And after this, we want to process the computation. If we think about a single query, what all is required for updating a range? All we need is to do is add to `l`, and then this same no. to all nos. from `l+1` to `r`. We know that this is same as doing a prefix sum on an array with all zeroes and `a[l]` = `x`. Lets observe:

`[0 0 0 0 0 0 0]` . query: `[1 5 2]`
`[0 2 2 2 2 2 2]`. Now if we just add 2 to `l` and do a prefix sum, then the `(r+1)th` value also gets 2. so to cancel the effect of the prefix sum, we subtract 2 form `r+1`

Now we know that for one query, doing 2 updates and a prefix sum gives us the required `diff` array. For multiple updates, we can do the 2 updates for all queries and then take the prefix sum at the very end. This works as addition is commutative and associative.
Overall complexity: $O(n+q)$

### LCA : lowest common ancestor

The best source to read would be : [cp-algorithms](https://cp-algorithms.com/graph/lca_binary_lifting.html)

### The main solution

If we had an array, we would have solved the problem. But what we have is a tree. so things are a little trickier. We somehow want to use the same ideas as that of an array and solve the problem. Key observations:

- evey simple path `u to v` can be broken as `u to l` and `l to v`, where `l` is the lca of `u v`.
- ```
p
|
l
/ \
/ k
u \
v

  We want to add 1 to the nos. from `u to v`. So we want to add 1 to the nos. in path `u...l` and `v...k`.
- In an array, we take prefix sum in the direction of l to r.
- So here we have two choices for the direction: `l to u and k to v` or `u to l and v to k`.
- If we take the latter, then the sum needs to be computed for inner nodes first(starting at leaves). Well, this is easy for us as we have dfs!!
- So, all we need to do is `a[u]+=1`, `a[p]-=1`, `a[v]+=1`, `a[l]-=1`.
- Now, as there will be prefix sums coming from the children of a node, this is a classic problem of tree dp.
`dp[u] = prefix sum till u`. `dp[u] = (sum over all child v :(dp[v])) + a[u]`. This can easily be computed using a dfs.

My code: [code](https://cses.fi/problemset/result/2405848/).