0
$\begingroup$

There are n houses in a city T, some of which are connected by streets in such a way that there is exactly one path between any two houses (i.e. the graph of houses and streets is a tree T).

Tanya has already prepared $m$ gift bags but she ran into a problem. After all, she herself also needs to find a house in the city of T for the celebration of the New Year. The distribution of gifts, as usual, will be done by deer.

You can give exactly one bag to one deer and send it on its way. At the same time, deer do not walk along the same street twice. The i-th bag is intended for residents of all houses on the path from $a_i$ to $b_i$. Therefore, it is considered that the deer can be given the i-th bag of gifts if he can leave the place where Tanya is celebrated and go through all the houses on the way from $a_i$ to $b_i$ without going through the same street twice -- that is, there should be a linear path from the starting location to house $b_i$, starting at house $a_i$.

How do we efficiently compute the maximum number of bags with gifts that Tanya can give away if she chooses the optimal house for the celebration.

We know that given a choice of root vertex she can give away a big of gifts that is supposed to travel on a route from $a_i$ to vertex $b_i$ if the least common ancestor of $a_i$ and $b_i$ is just $a_i$, so we could compute it in O(n*m) but it should be possible to do it faster.

The input consists of the following:

First we specify the number of vertices $n$.

Then we have $n-1$ edges given as $x_i, y_i$.

Then we have a number $m$ followed by $m$ lines that indicate what routes we want to deliver bags along

Each line is of the form $a_i$, $b_i$.

Source: https://algocode.ru/files/course_ap2021/contest-24956-ru.pdf

$\endgroup$
5
  • $\begingroup$ What are $a_i$ and $b_i$? Are those vertices? If that's the case, how is $(a_i, b_i)$ a "bag"? There are some details to clear out in your post. $\endgroup$
    – Nathaniel
    Commented Dec 27, 2022 at 23:47
  • $\begingroup$ We are given a list of pairs of vertices which represent start and endpoints for routes that we want the deer to deliver the bags along. $\endgroup$ Commented Dec 27, 2022 at 23:55
  • $\begingroup$ Please credit the original source for where you encountered this task. Regarding requests for feedback, please edit the question to address feedback (don't leave clarifications in the comments). Thank you! $\endgroup$
    – D.W.
    Commented Dec 28, 2022 at 0:34
  • $\begingroup$ What qualifies as "going through the same street twice"? Is going backwards along the street acceptable, or does there need to be a linear path from Tanya's house to a_i to b_i? $\endgroup$
    – LogicalX
    Commented Dec 28, 2022 at 16:09
  • $\begingroup$ The latter, there should be a linear path from the start, through a_i to b_i. $\endgroup$ Commented Dec 28, 2022 at 16:39

1 Answer 1

1
$\begingroup$

It should be possible to solve the problem in O(NlogN+M) time. I don't currently have a functional algorithm, but here's an outline of my first thoughts that may help. What I thought of was a mix of DFS and a sweeping line algorithm, starting at a leaf node. A key observation seems to be that starting on all nodes on the side of the a_i node that doesn't have b_i on it will allow Tanya to give that gift while starting on the side with the b_i will not allow Tanya to give the gift. If only we knew which side each b_i was on, relative to each a_i, then we would be able to solve the problem easily.

Algorithm outline:

  1. Input the graph as an adjacency list.

  2. Keep a map mapping all the a_i's to b_i's and all the b_i's to a_i's. Call this map C.

  3. Keep a set of all the a_i's A.

  4. Keep an array of booleans D of size N, initialized to all be false. This will record whether each node has been visited.

  5. Preparation for DFS.

    a. Keep an array gifts of size N to store the number of gifts we can give if we start at each node.
    b. Keep an integer k, initialized to 0. This will be the amount by which the values of the graph are offset.
    c. Find an arbitrary leaf node v by looping through the adjacency list and finding a node with only one edge. This will be the starting point for the DFS.
    d. Initialize gifts[v] by setting it equal to m, and initialize D[v] by setting it to true.

  6. Start DFS at v. For every node w:

    a. If w is in the set A and D[C[w]] is false (w is an a_i and its corresponding b_i has not been visited), set gifts[next unvisited child of w] to be gifts[w]-1. Continue DFS from that child.
    b. Else if 'w' is in the set A and D[C[w]] is true (w is an a_i and its corresponding b_i has been visited), set gifts[w] to be gifts[w]+1. Set k to k+1. Continue DFS from the next unvisited child of w.
    c. If neither of the above statements is true, then set gifts[next unvisited child of w] to gifts[w]. Continue DFS from that child.
    d. Update D to show that the new node in the DFS is now visited.

  7. Analyze results. For each node w, the number of gifts Tanya will get by starting from that node will be gifts[w]-k. The answer you're looking for will be the maximum value of this over all possible w.

If you've read this far, try working this algorithm out on a sample test case.

Note that right now the solution doesn't work 100% -- when the a_i and b_i are on separate branches and the DFS reaches the a_i first, the algorithm will return the wrong answer. Perhaps this is fixable while still maintaining a good runtime, or perhaps we need a different way of traversing the graph (other than DFS).

The time complexity of the above algorithm is O(NlogN+M) as DFS goes through N nodes and the complexity for each node is O(logN) from checking whether node w is in set A, while preprocessing of the M paths gives the +M.

$\endgroup$
1
  • $\begingroup$ I made the letters sub-bullets in the editor but for some reason that didn't carry over into the actual answer. Sorry if it's hard to read. $\endgroup$
    – LogicalX
    Commented Dec 28, 2022 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.