You are given a tree with N nodes, each node has an associated cost. You need to answer M questions of the type: "which is the maximum cost of a path that contains node Q?".
The first line of the input contains two integers N and M (1 ≤ N, M ≤ 100.000). The second line contains N integers representing the cost of the nodes ( - 20.000 ≤ cost ≤ 20.000). Each of the next N - 1 line contains two integers representing an edge between two nodes. On each of the next M lines there is a single integer Q corresponding to a question.
The output should contain M lines. On line i print a single integer representing answer for the i-th question.
5 2
-3 4 5 6 3
1 2
1 3
2 5
2 4
1
2
12
13
You are given a tree consisting of N nodes and N - 1 weighted edges. You want to remove exactly M edges so that node 1 will remain in a component with exactly K nodes, while minimizing the sum of costs of the removed edges.
The first line of input will contain three positive integers N(1 ≤ N < 75), M(1 ≤ M < N) and K(1 ≤ K ≤ N). The following N - 1 lines will each contain 3 numbers x y c, describing an edge between nodes x and y of cost c.
The first and only line of your output should contain one integer representing the minimum cost required, or - 1 if there is no valid solution.
10 4 3
1 2 10
1 3 21
1 4 4
2 7 2
3 5 5
3 6 12
6 8 7
6 9 6
6 10 3
23
Steven wants to start his own wheat farm. In order to do so, every land patch needs to meet some strict regulations regarding the pH and Feng Shui index. Luckily for him, he can change the value of the pH or Feng Shui index by one for one dollar.
Steven knows N types of land patches and their pH and Feng Shui indexes. Unfortunately, due to bad legislation, some patches can become forbidden and others can become permitted.
Steven must answer to three types of queries. What's the minimal cost to transform a land patch to a valid one? A land patch becomes forbidden, A land patch becomes permitted.
The first line contains a positive integer N (1 ≤ N ≤ 250 000) - the number valid land patches in the beginning. The next N lines contain two positive integers p, h ( - 228 ≤ p, h ≤ 228) - the pH index and the Feng Shui index of the land patch.
The next line contains a positive integer M (1 ≤ M ≤ 250 000) - the number of queries. The next M lines contain three integeres t, p, h (0 ≤ t ≤ 2, - 228 ≤ p, h ≤ 228) - the type of the query, the pH index and the Feng Shui index.
If the type is 0, you must answer Steven what's the minimal cost to transform the land patch defined by the pH and the Fend Shui index to a current permitted one.
If the type is 1 the current land patch becomes permitted and if the type is 2 it becomes forbidden.
One land patch can become permitted multiple times, even if was already permitted, but one query that makes it forbidden overrides it. This applies both ways.
For each of Steven's questions, provide the minimal cost to transform the queried land patch into a land patch that is valid at that current time.
4
2 3
1 1
0 0
5 7
4
1 5 6
0 5 5
2 1 1
0 1 1
1
2
Pay attention to the memory limit for this problem!
You are given an array A of size N and a positive integer S. You need to find the number of ways W in which you can chose 5 elements with distinct positions such that their sum is equal to S.
The first line contains two positive integer N, S (1 ≤ N ≤ 103, 0 ≤ S ≤ 2 * 109) - the size of the array and the queried sum.
The next line contains N numbers Ai (0 ≤ Ai ≤ 4 * 108, 1 ≤ i ≤ N).
Print the only integer W (0 ≤ W < 231) - the number of ways to chose the elements.
6 5
1 1 1 1 1 1
6
The minister of transport of Byteland decided he needs to increase his popularity in order to aspire for presidency. Therefore, he wants to create a program that will maintain a system of transport vital to the country.
For now he is interested in the most important N cities and he wants the system of transport to contain N - 1 roads in such a way that each city is connected to the capital (the city labeled with 1) and the total maintenance cost of the streets is as small as possible. Even though he found the optimal solution, in the future, M new roads will be built between the N cities so sometimes it might be better to modify the system of transport in order to have a minimum cost.
The first line of the input contains a single integer N. Each of the next N - 1 lines contains information about the initial system of transport. On line i there are two integers K and C, representing the city closest to capital that is connected to city i and the cost of maintenance of the street connecting these two cities. If the city is directly connected to the capital then K = 1.
Line N + 1 contains an integer M. Each of the next M lines contains 3 integers X, Y and C, representing the fact that a new road is build between cities X and Y, having a maintenance cost equal to C.
The output should contain M lines. On line i print a single integer representing the minimum cost of the system of transportation after the first i roads have been built.
9
1 4
2 6
1 10
3 6
3 7
5 2
2 3
2 6
6
8 4 3
3 1 3
8 1 3
3 7 6
6 7 4
5 2 2
37
34
33
33
30
26
Given 
points on a plane, output the area of a rectangle with its sides parallel with the coordinate axes that contains inside or on the sides at least 
points of the points given.
The input file drept.in contains on the first lines 2 numbers 
and each of the following lines contains 2 numbers 
and 
describing the th point.
The output file drept.out contains the required area.
13 7
5 5
7 8
6 8
5 8
4 6
6 3
4 2
8 0
9 2
3 4
7 8
5 4
5 3
10
You are given N segments in the xOy plane. Find the shortest closed broken line that contains all the given segments. A closed broken line is defined as a series of segments A[1] - A[2], A[2] - A[3] ... A[K - 1] - A[K], A[K] - A[1], where A is an array of points on the plane. The line can intersect itself.
The first line contains T, the number of tests to follow. Then T tests follow. For each test, the first line contains an integer N(
), followed by N lines, each describing a line segment by giving 4 real numbers, the x and y coordinates of the first end of the segment, and then the x and y coordinates of the second end of the segment.
Your output file should contain T real numbers, representing the minimum length of the shortest closed broken line containing all the line segments. Your output should have a precision of 1.e - 6.
2
2
1 1 1 2
1 1 2 2
3
-931.693980 781.297764 -767.512077 1305.542158
933.100984 -166.303237 1225.734021 -125.170151
320.771418 -163.911119 -148.087080 -332.428961
1.000000
4427.669962
You are given a directed graph with 
nodes and 
edges. You can say that node 
controls node 
if you can reach node from node only using the edges in the graph. For each node 
in the graph, you must print the number of nodes that node controls.
The first line contains (
), the number of nodes. lines follow. Each line starts with a number 
, followed by numbers, representing the nodes that has an edge to. It is guaranteed that the sum of the numbers is less than 
. Also, there are no more than 
maximal subsets of nodes such that for any edge 
in the subset, there is a series of edges connecting with .
You must print numbers on the first line, separated by a blank space, where the th number represents the number of nodes controlled by .
7
2 5 2
0
1 2
3 3 5 1
2 1 2
3 1 2 3
3 2 5 6
3 1 2 5 3 5 6
Given an array of positive integers, count the number of substrings with the following properties:
- it has length of at least 2
- its extremities are bigger than the other elements (e.g. 2 2 3 is bad, but 3 2 3 is good)
The input will contain on the first line one integer 
(
. The second line contains 
numbers 
and the array for which we want the solution is obtained as following: 
. Both arrays and 
are 0-indexed.
The output will contain the number of substrings with the given properties.
3
3 2 3
2