AlgorithmsThread Tree Basics Contest
A. Circumference of a Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hopefully you know how to find the diameter of a tree. That's the first part of tree basics, after all! But this problem is completely different: now, you need to find the circumference of a tree!

As you probably know, pi is equal to the ratio between something's circumferance and its diameter. Also, as you may not know, math is a lie and pi is really equal to 3. Rumor has it, this is where the number tree(3) comes from.

Assuming pi equals 3, what is the circumference of the given tree?

Input

The first line will contain a single integer $$$n$$$, the number of nodes in the tree. $$$n-1$$$ lines follow, each containing two different integers, describing the edges of the tree. Additional constraint on input: these edges will form a tree.

$$$1 \leq n \leq 3*10^5$$$

Output

Output a single integer: the circumference of the tree.

Examples
Input
1
Output
0
Input
3
3 2
2 1
Output
6
Input
5
4 2
1 4
5 4
3 4
Output
6

B. Dynamic Diameter
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n+1$$$ nodes and $$$n-1$$$ edges where the first $$$n$$$ nodes are a tree and node $$$n+1$$$ is in its own component. For each node $$$i$$$ from $$$1 ... n$$$, answer the following question:

If an edge was added from node $$$i$$$ to node $$$n+1$$$, what would the diameter of the created tree be? (Notice that the $$$n+1$$$ nodes will be a tree if this edge was added).

Input

The first line will contain a single integer $$$n$$$, the number of nodes in the tree initial tree. $$$n-1$$$ lines follow, each containing two different integers, describing the edges initially in the tree. Additional constraint on input: these edges will form a tree on the first $$$n$$$ nodes.

$$$1 \leq n \leq 3*10^5$$$

Output

Print $$$n$$$ integers, each on their own line. The $$$i$$$th is the diameter of the new tree if you were to add an edge from node $$$i$$$ to node $$$n+1$$$.

Examples
Input
1
Output
1
Input
3
3 2
2 1
Output
3
2
3
Input
5
4 2
1 4
5 4
3 4
Output
3
3
3
2
3

C. Sloth Naptime
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As probably know, sloths live on trees. Accordingly, David has a pet sloth which he lets play on his unweighted trees when he solves programming problems. Occasionally, David will notice that his sloth is located on a particular node $$$a$$$ in the tree, and ask it to move to some other node $$$b$$$.

Of course, the sloth is as well-intentioned as can be, but alas, it only has enough energy to move across at most $$$c$$$ edges. If the sloth needs to cross fewer than $$$c$$$ edges to get to node $$$b$$$, it will get there and then take a nap. Otherwise, it will get as close as possible before it retires and hangs idly awaiting further digestion.

Where will the sloth end up? Also, since this happens quite often, David would like you to answer $$$q$$$ queries, each one of the similar form.

Input

The first line will contain a single integer $$$n$$$, the number of nodes in the tree. The following $$$n-1$$$ lines will contain two integers $$$u$$$ and $$$v$$$, describing the edges in the tree. These edges will form a tree.

After that, there will be a single line containing an integer $$$q$$$, the number of times David will motivate his sloth to move. $$$q$$$ lines follow, each containing three integers $$$a$$$, $$$b$$$, and $$$c$$$: the node the sloth starts on, the node David asks the sloth to move to, and the energy the sloth has when starting.

$$$1 \leq n, q \leq 3*10^5$$$

$$$1 \leq a, b, c, u, v \leq n$$$

Output

For each query, output a single integer: the id of the node that the sloth must sleep at.

Examples
Input
1
1
1 1 1
Output
1
Input
3
3 2
2 1
3
2 2 2
1 1 2
3 3 3
Output
2
1
3
Input
5
4 2
1 4
5 4
3 4
5
3 5 2
3 5 4
1 5 5
4 5 4
1 5 4
Output
5
5
5
5
5

D. Cycle Free Flow
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected connected weighted graph of n nodes which contains no cycles. For q different pairs of nodes, we would like you to find the maximum flow from the first node in the pair to the second node in the pair. See the definition for max flow below if you don't know what it means.

Also, please answer these queries online. Originally, I was going to force you to do this by encrypting stuff, but that would make this problem harder to read and more annoying. So, on your honor, please answer the first query before reading the second query, et cetera. After all, this is just practice for you to get better, right?

The maximum flow in a graph between two nodes $$$a$$$ and $$$b$$$ can be defined as follows: You may pick any path from $$$a$$$ to $$$b$$$ such that every edge on that path has a positive weight. Then you may subtract 1 from the weight of every edge on that path, and add 1 to your answer. Keep doing this as many times as you would like. The "maximum flow" between the two nodes is the greatest that your answer could possibly be, if you choose your paths optimally at every step.

Input

The first line will contain a two integers: $$$n$$$ and $$$m$$$, the number of nodes and the number of edges in the graph. The next $$$m$$$ lines will each contain three integers: the endpoints $$$u$$$ and $$$v$$$ of an undirected edge, and the initial weight of that edge $$$w$$$.

The next line will contain a single integer $$$q$$$: the number of queries you must answer.

Each of the next q lines will contain two integers: $$$a$$$ and $$$b$$$, the two nodes you should find the max flow between.

$$$2 \leq n, m, \leq 3*10^5$$$

$$$1 \leq a, b, \leq n$$$ $$$a \neq b$$$

$$$1 \leq w \leq 10^{9}$$$

$$$u \neq v$$$

Additional constraint on input: the given graph is connected and has no cycles, self-loops, or multi-edges.

Output

For each query, please print a single integer: the max flow between nodes $$$a$$$ and nodes $$$b$$$ for that query.

Examples
Input
2 1
1 2 2768
2
1 2
2 1
Output
2768
2768
Input
3 2
3 2 4814
2 1 1832
3
2 1
1 2
3 1
Output
1832
1832
1832
Input
5 4
4 2 10348
1 4 2690
5 4 9807
3 4 8008
5
5 4
1 5
5 4
5 4
1 5
Output
9807
2690
9807
9807
2690
Input
5 4
1 3 2653
4 1 322
5 1 8657
2 4 4896
5
4 2
2 5
2 5
1 3
4 5
Output
4896
322
322
2653
322

E. Filthy Rich Trees
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You may have heard the saying "money doesn't grow on trees." Obviously, whoever came up with it stunk at both botany and programming. You've learned that creating trees which grow obscene amounts of money is so trivial, that it's left as an exercise to the reader. Time for the real challenge: profiting off your invention!

You have rooted your money-tree at node $$$1$$$, and each node has a specified moola value. The amount of money that some subtree rooted at node $$$x$$$ will produce is equal to the product of the moola values of all nodes in $$$x$$$'s subtree. Initially, all nodes will have a moola value of 1.

Now, $$$q$$$ times, one of two things happen, given to you in the form of "t x y":

If $$$t = 1$$$, you give node $$$x$$$ a special fertilizer which sets its moola value to $$$y$$$.

If $$$t = 2$$$, a customer comes in and asks "how many times more valuable is subtree $$$x$$$ than subtree $$$y$$$"? Formally, what is the value of subtree $$$x$$$ divided by the value of subtree $$$y$$$. Also, you don't like printing massive numbers, so subtree $$$x$$$ is more than $$$10^9$$$ times greater than subtree $$$y$$$, only print "1000000000".

Input

The first line will contain a single integer $$$n$$$, the number of nodes in the tree. $$$n-1$$$ lines follow, each containing two different integers, describing the edges of the tree. Additional constraint on input: these edges will form a tree.

After that there will be a single integer $$$q$$$: the number of queries. $$$q$$$ line follow, each of the form $$$t x y$$$, as described above.

$$$1 \leq n, q \leq 3*10^5$$$

$$$1 \leq t \leq 2$$$

$$$1 \leq x, y \leq n$$$

Output

For each query of type 2, print a single line with one real number: how many times more valuable subtree $$$x$$$ is than subtree $$$y$$$. HOWEVER, if this value is >= $$$10^9$$$, then print just $$$1000000000$$$ instead.

Your answer will be accepted if your answers to all queries have absolute or relative error of at most $$$10^{-6}$$$.

Examples
Input
1
1
1 1 1
Output
Input
3
3 2
2 1
3
2 2 2
2 1 2
2 3 3

Output
1.0000000000
1.0000000000
1.0000000000

Input
5
4 2
1 4
5 4
3 4
5
2 5 2
1 5 4
1 5 5
1 5 4
2 5 4

Output
1.0000000000
1.0000000000

  







        

        





    
        
F. The Lorax
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I am the Lorax, and I speak for the Trees!
Plant many of them, plant many now please,
We all live in Thneedville, a connected component,
that has $$$n$$$ nodes and $$$n-1$$$ edges this moment,
$$$q$$$ times we'll make $$$x_i$$$ seeds and the same number of pots,
but in different places, believe it or nots.
Match each seed with a pot, and each pot with a seed
But match in a way that's special indeed:
The total sum of the distances between every pair
must be minimized to keep clean the air.
But if $$$x_i$$$ is zero and there is no objection,
we'd like you to answer the following question:
If you were to match everything now in the way you've been told
How many pairs would cross this given road?
**This problem has the same idea, data, and samples (but different flavor-text) as another problem written for a training camp by Travis Meade, and tested by myself. Seems to me to be a notorious coincidence. :)
Input
The first line will contain a single integer $$$c$$$: the number of test cases.
For each testcase, the first line contains $$$n$$$ and $$$q$$$: the number nodes in Thneedville, and the number of queries. $$$n-1$$$ lines follow, each containing a pair of integers describing the edges in Thneedville.
$$$q$$$ lines follow, each of the form $$$a$$$ $$$b$$$ $$$x_i$$$ . If $$$x_i$$$ is zero, we are asking about the number of matched pairs that cross the edge from $$$a$$$ to $$$b$$$ (there will always be an edge directly connecting $$$a$$$ to $$$b$$$). Otherwise, it indicates that we have created $$$x_i$$$ seeds at node $$$a$$$, and $$$x_i$$$ pots at node $$$b$$$.
$$$c \leq 20$$$
$$$1 \leq n, q \leq 10^5$$$
$$$1 \leq a, b \leq n$$$
$$$0 \leq x_i \leq 10^8$$$
Output
For each query in which $$$x_i$$$ is zero, print a single integer: the number of pairs crossing the queried edge.
Example
Input
2
6 5
1 2
2 3
3 4
4 5
4 6
1 6 2
2 5 3
4 3 0
6 2 2
4 3 0
4 6
1 2
1 3
4 1
1 2 0
3 4 5
4 2 1
1 3 0
1 4 0
1 2 0

Output
5
3
0
5
4
1