### PROBLEM LINK:

**Setter :** Mohammad Salik

**Tester :** Hasan Jaddouh

**Editorialist :** Mohammad Salik

## Difficulty

Medium-Hard

## Prerequisites

Square root decomposition on trees, DFS, LCA(Lowest Common Ancestor ), Inclusion-Exclusion, Binary Search

## Problem

Given a tree with N nodes and each edge having a cost and Q queries on it.All the queries are to be answered online. Query is described by eight integers U,V,X_{1},Y_{1},X_{2},Y_{2},X_{3},Y_{3}. The answer to each query is the sum of all such costs C which are encountered in the unique path from U to V and which satisfy the following conditions :

- If
**C**is a multiple of 2,**C**must be between**X**and_{1}**Y**inclusive._{1} - If
**C**is a multiple of 3,**C**must be between**X**and_{2}**Y**inclusive._{2} - If
**C**is a multiple of 5,**C**must be between**X**and_{3}**Y**inclusive._{3} -
**C**must be a multiple of 2, 3 or 5.

## Explanation

Let us root the tree at 1. Throughout the editorial we will assume the tree to be rooted at 1.

### For Subtask 1

The constraints for this subtask are low enough for brute force to pass. One can simply trace the path from U to V and decide for each cost whether to include it or not based on the four given conditions. This solution works in O(Q*N) i.e O(N) time for each query.

### For Subtask 2

Lets make some crucial observations which will help us in solving the problem :

### How to Compute answer(X) for a node X for any current query with the parameters $X_{1},Y_{1},X_{2},Y_{2},X_{3},Y_{3}$ ?

We will have to first do some precomputation i.e before any queries. Let us first define blocksize.Just for now assume blocksize=500. Let us now find all the nodes i for which depth[i]\%blocksize==R (Assume R=1 just for now for the sake of simplicity) where depth[i] is the distance of the node from the root.Let us call all such nodes special nodes i.e for which the condition depth[i]\%blocksize==1 is true.For all such nodes maintain 7 vectors.Let V[i][x] denote the vector for special node i such that it stores all the multiples of x along the path from that node to the root.vectors will store the costs for 7 values of x i.e 2,3,5,6(2*3),10(2*5),15(3*5),30(2*3*5). Now we will sort all these vectors for all the special nodes and for all the seven values for these special nodes.We will maintain a prefix sum array pre[i][x] also to get the prefix sum for any of the 7 multiples of any special node. pre[i][x][k] (k < pre[i][x].size())

Now suppose we wish to find answer(X) for any query.Let Res denote the final answer.Res=0 initially.Now two cases arise :

Now once we reach a special node P we have to find the answer from this node to root and add it to Res.Now we have to find the answer(P) for special node P. Here comes the inclusion-exclusion.

answer(P)= Sum of multiples of 2 in range X_{1} to Y_{1} in V[P][2] + Sum of multiples of 3 in range X_{2} to Y_{2} in V[P][3] + Sum of multiples of 5 in range X_{3} to Y_{3} in V[P][5] - sum of multiples of 6 in union of ranges [X_{1},Y_{1}] & [X_{2},Y_{2}] in V[P][6]- sum of multiples of 10 in union of ranges [X_{1},Y_{1}] & [X_{3},Y_{3}] in V[P][10] - sum of multiples of 15 in union of ranges [X_{2},Y_{2}] & [X_{3},Y_{3}] in V[P][15] + sum of multiples of 30 in union of all the 3 ranges in V[P][30].

Now sum of multiples of 2 in range X_{1} to Y_{1} in V[P][2] can be calculated by using binary search on the V[P][2] vector and by using the prefix sum vector pre[P][2] to calculate the sum.Similarly all the other values can be calculated using binary search.

So the query takes approx O(blocksize) time.

In the above appropriate value of blocksize can be set to blocksize= sqrtN. Also above R was taken to be 1 for the condition of special node. In fact this value should be calculated by running an initial dfs and finding the frequency of depth[i]\%blocksize for all i and hence calculating an appropriate R such that number of nodes satisfying depth[i]\%blocksize==R is as minimum as possible. This is done to minimize the number of special nodes and save both memory and time.

## Time Complexity

O(Q*sqrtN)

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.

Testerâ€™s solution can be found here.