In country X, there are $$$N$$$ villages numbered from $$$1$$$ to $$$N$$$. There are $$$N - 1$$$ roads, and each road connects two different villages. Each road is numbered $$$1, 2, ..., N - 1$$$, with road $$$i$$$ connecting village $$$x_i$$$ to village $$$y_i$$$.

For any two villages in country X, there is exactly one route connecting them. A route passes through a sequence of distinct villages, and its length is the number of roads on the route.

The government needs to select some villages to build gas stations. According to the law, gas stations must be placed in such a way that for any route of length $$$k$$$, there is at least one village with a gas station. Determine the minimum number of gas stations that need to be placed.

$$$Input:$$$

The first line contains two integers $$$N$$$ and $$$k$$$.

Each of the following $$$N-1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$.

$$$Output:$$$

Print the minimum number of gas stations.

$$$Constraint:$$$

$$$1 \le x_i, y_i \le N$$$, $$$x_i ≠ y_i$$$.

$$$1 \le k \le N - 1$$$.

Subtask 1: $$$2 \le N \le 3000$$$.

Subtask 2: $$$2 \le N \le 2.10^5$$$.

$$$Example:$$$

Input:

7 2

1 2

1 3

2 4

2 5

4 6

6 7

Output:

2

Explain: We can put a gas station on nodes 2 and 6 or 2 and 7,...

I need help with subtask 1, but if you can, can you also assist in doing subtask 2? Tks

Given an array $$$a$$$ containing $$$n$$$ elements and you will have $$$q$$$ queries. Each query denote by $$$l$$$, $$$r$$$, $$$x$$$.

You have to check if from index $$$l$$$ to $$$r$$$, is there any element equal to $$$x$$$ or not.

Contraint:

$$$n$$$, $$$q$$$ $$$\le$$$ $$$10^5$$$

$$$1$$$ $$$\le$$$ $$$l$$$ $$$\le$$$ $$$r$$$ $$$\le$$$ $$$n$$$

$$$1$$$ $$$\le$$$ $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ $$$\le$$$ $$$10^9$$$

$$$1$$$ $$$\le$$$ $$$x$$$ $$$\le$$$ $$$10^9$$$

Input:

The first line contains two integers $$$n$$$ and $$$q$$$

The second line contains $$$n$$$ integer $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$

Then each of the next $$$q$$$ lines contains three integer $$$l$$$, $$$r$$$, $$$x$$$

Output:

Print "YES" or "NO" in each query if $$$x$$$ is in range $$$l$$$, $$$r$$$

For Example:

6 4

1 2 3 4 5 6

1 2 1

3 4 2

1 6 7

2 5 3

Then output is:

YES

NO

NO

YES

Help me pls. Sorry for bad English

Given a string, the task is to count all palindrome sub string in a given string. Length of palindrome sub string is greater than or equal to 1.

Constraint:

length of s <= 1e5

For example:

Input:

ata

Output:

4

Input:

aabbaa

Output:

11

Explanation: [a], [a], [b], [b], [a], [a], [aa], [bb], [aa], [abba], [aabbaa]

Can you guys help me please, I can't come up with any ideas to do this problem.

I found a problem of count subset which sum equal to K in a web but the constraint in this problem is so big, I don't know if this problem can be solved or not, can you guys help me pls ?

Given n and k, array a consisting of n elements.

1 <= n,k <= 1e5

Ai <= 1e5

For example:

Input: 6 90

70 50 60 20 30 40 Output: 4

Explanation : [70, 20], [60, 30], [50, 40], [20, 30, 40]