Hello why does https://www.codechef.com/viewsolution/28645771 give runtime error for this problem https://www.codechef.com/problems/TREEDGE ?

You are given a tree and a constant K. The nodes of the tree are numbered from 1 to N. Each node in the tree has a value associated with it, A[i], where A[i] is either 1 or 0.

A tree is considered beautiful if the sum of its node values is equal to the given constant, K.

Georg wants to make the tree beautiful by removing any number of nodes (and their edges) from the tree, such that the tree still remains connected.

Your task is to count the number of ways to make the tree beautiful and print it modulo 10^9 + 7. Input format: Two integers N and K on the first line followed by the values of the N nodes in the next line. Lines 3 to (N + 1) contain the edges, where each pair of numbers indicates an undirected edge between those nodes.

Sample Input:

5 2
0 1 0 1 1
1 2
1 3
1 4
2 5

Output: 5

Constraints: N <= 1e5, K <= 100

Please help me with this problem. It feels like a DP on trees problem, but I’m unable to find the recurrence.

I'm getting wa31 for this problem ( my submission ).

First, I find all vertices that can be reached from the capital. Then, I look at all vertices which have indegree equal to 0. These vertices must have an edge directly connecting them to the capital and can obviously be visited in any order. Now, if unvisited vertices remain, they must form a cycle. I visit these vertices next ( again, in any order).

Please help

Edit : I'm getting wa32 now:(

I am sorry if this sounds spammy or anything but I've been trying to solve this for a while now. I'm unable to get past the tenth test case. I feel like my mistake is very subtle so if you find it, please tell me. Thanks!

Code

codeforces.com/blog/entry/60083

In the editorial for problem E, how does the author descend down the segment tree to find the leftmost maximum element? It hasn’t been explained there.

Edit: I’ve understood how to go down the tree, but I’m unable to convince myself that its complexity is O(logn) per query. Please help.

I’ve though about this for a couple hours but I’m unable to make much headway. It goes like this :

You have an array of size n and q queries. Each query is of the form (l, r, k). The answer to each query is the index (1-based) of the leftmost number in the range [l, r] which is greater than or equal to k. If there is no such value, return -1. Constraints: n, q <= 1e5, l <= r and the elements can be from 0 to 1e9. The program should run within a second.

Example input :

n = 5, q = 2

7 4 6 9

Queries :

3 4 7

2 4 5

Output:

4

3

I feel like a maximum segment tree might work here, but I am unable to put it together. Please help. Obviously, a O(n^2) solution would not run in time. I think the intended solution is O(nlogn).