Same here... I tried to do second one but I was messing up when we have traversed one task point and best case is from some other one which comes after that...

For the first one I think you just need to remove all the leaf in tree which doesn't have coins, then answer will be 2* number of edges.

Second one standard dijkstra algorithm.

This is just a rough idea yes still we need to handle other cases

For the first one I kept on removing the leaf nodes, given they had no coin(just another variation of topological Sort). It was mentioned that if the distance between nodes was less than 2, we could still collect coin from either of them. So, I removed the leaf nodes again for two iterations(This time without checking if there is a coin at the leaf or not). Counted the number of edges in the leftover tree and returned (number of edges)*2, as i had to return at the same vertex after traversing the tree. Tried to solve the second via same logic, but I couldn't figure out how to find the minimum path.

I found the exact question as first on leet code Search — leet code 2603

I think second problem is from codefoces around 1800 rated

here is similar question of second problem from codeforces F. Vlad and Unfinished Business

First Problem : Your text to link here...

Hey, same here was not able to solve any of them, but I found the second problem here, https://mirror.codeforces.com/blog/entry/118645 , and what do you think about the expected rating, because I was literally feeling sad after the OA

For the second problem this might work=>We make the start node root of tree and for each node store the count of nodes in it's subtree that are in task array, also store for a node if the end node is in it's subtree now after doing this we start second DFS from the start node and look at its children nodes now if the child node has count 0 then we won't do dfs for it else if a node has count> 0 but also has end node inside that subtree then we will ignore it for now and check if there is any other child with subtree count>0 and explore that first, we will also keep a global count variable and will do count-- if any node from the task is visited, now as soon as we get count=0 and current node=end node we will return the ans(no.of edges traversed in complete traversal).

The first question was exact replica of leetcode 2603. Although, I was also unable to solve either of them.

Those mcq's deserve upsolving of their own too.

no mercy walkthrough of the second problem

• harvest the minimal subtree that ties together start, end and every task node. let its edge count be m.
• a depth-first rampage hits every one of those edges twice → 2 m.
• but we quit at end, so we skip retracing the unique path of length d = dist(start,end).
• brutal truth: total time is 2 m − d.

from collections import deque
import sys

sys.setrecursionlimit(1 << 20)

def get_minimum_time(tree_nodes, tree_from, tree_to,
                     start_node, end_node, task_nodes):
    # build adjacency
    adj = [[] for _ in range(tree_nodes + 1)]
    for u, v in zip(tree_from, tree_to):
        adj[u].append(v)
        adj[v].append(u)

    # mark required nodes
    required = [False] * (tree_nodes + 1)
    for x in task_nodes:
        required[x] = True
    required[start_node] = True
    required[end_node] = True
    total_req = len(task_nodes) + 2  # start and end are distinct

    # dfs post-order to count required nodes per subtree
    parent = [0] * (tree_nodes + 1)
    order = []
    stack = [1]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                stack.append(v)

    need = [1 if required[i] else 0 for i in range(tree_nodes + 1)]
    edges_in_sub = 0
    for u in reversed(order):
        p = parent[u]
        if p == 0:
            continue
        need[p] += need[u]
        if 0 < need[u] < total_req:
            edges_in_sub += 1

    # bfs distance between start and end
    dist = [-1] * (tree_nodes + 1)
    q = deque([start_node])
    dist[start_node] = 0
    while q:
        u = q.popleft()
        if u == end_node:
            break
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)

    return 2 * edges_in_sub - dist[end_node]

The second problem can be taken as a variation of this problem from a recent cf round 2071C - Trapmigiano Reggiano

If anyone is curious such problems involving 2*number of edges in a minimal subtree are also knows as steiner subtree problems !

In the second problem. I believe we can do the following :

Root the tree at the start node. Find in times for all the nodes. Sort the given list of nodes along with the end node with respect to their in times. Now, we need to visit all the nodes and return at the end node. We can see that it is always better for us to visit nodes in sequence of the new sorted list either from the start or the end of this list. So, we may either start from the first node of this sorted list, keep moving until we come across end node. We jump at the last node of this list and follow the list in reverse to ultimately finish at the end node. Or we may do the same process starting from the last node of the sorted list, jump at the first node and finish at the end node.

Edit : This may work for problems with multiple queries but a much easier solution exists for $$$q = 1$$$.

Hi, I got the First One in 28 mins, I dont know if it will pass all the test cases or Not, Intuition is Simple-> Since all the Leaf nodes, not containing the Coins will have no contribution so eliminate them, then, from remaining nodes, since we can get the coin 2 nodes away, simply remove leaf nodes 2 times, by looping 2 times, That's it ~~~~~ int f(){ // Given Input--<> vectorcoins,vector<vector>edges; int n = coins.size(); vector<vector> adj(n); vector deg(n, 0);

for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
        deg[e[0]]++;
        deg[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1 && coins[i] == 0) {
            q.push(i);
        }
    }

    vector<bool> removed(n, false);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        removed[u] = true;
        for (int v : adj[u]) {
            if (!removed[v]) {
                deg[v]--;
                if (deg[v] == 1 && coins[v] == 0) {
                    q.push(v);
                }
            }
        }
    }

    for (int times = 0; times < 2; ++times) {
        for (int i = 0; i < n; ++i) {
            if (!removed[i] && deg[i] == 1) {
                q.push(i);
            }
        }
        int sz = q.size();
        while (sz--) {
            int u = q.front(); q.pop();
            removed[u] = true;
            for (int v : adj[u]) {
                if (!removed[v]) {
                    deg[v]--;
                }
            }
        }
    }

    int ans  = 0;
    for(int i = 0;i<n;i++){
        if(!removed[i])ans++;
    }
    if(ans == 0)return 0;
    return 2*(ans-1);
}

~~~~~~ 2nd one is seeming a little bit different BTW I would really like to know, If it was onCampus or Off-Campus, I am from Tier-4,5, College so, Just asking

Could you tell what was asked in MCQs?