TheForces Round #38 (Tree-Forces)
A. Cyclic Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recall that an unrooted tree of size $$$n$$$ is an undirected connected graph with $$$n - 1$$$ edges.

Given an unrooted tree of size $$$n$$$, find two nodes $$$u$$$ and $$$v$$$, such that when the undirected edge $$$(u, v)$$$ is added to the tree, a simple cycle that consists of at least $$$3$$$ nodes is created.

It can be shown that under the constraints of the problem, an answer always exists.

Input

The first line of the input consists of a single integer $$$n$$$ $$$(3 \le n \le 100)$$$, the size of the tree.

On each of the next $$$n - 1$$$ lines, there are two integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n)$$$, representing an edge in the tree between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the input provides a valid tree.

Output

Output exactly two integers $$$u$$$ and $$$v$$$, such that when the edge $$$(u, v)$$$ is added to the tree, there is a cycle of size at least $$$3$$$.

Examples
Input
3
1 2
2 3
Output
1 3
Input
4
1 2
1 3
3 4
Output
1 4
Note

See the second example after the edge $$$(1, 4)$$$ is added:

A cycle of size $$$3$$$ that consists of nodes $$$1$$$, $$$3$$$, and $$$4$$$ is created. Another valid answer would be the edge $$$(2, 4)$$$, which would create a cycle of size $$$4$$$.

B. Tree Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Spyrosaliv and Cow the Cow are playing a game on a tree of size $$$n$$$.

Spyrosaliv will start at node $$$s$$$. Spyrosaliv and Cow the Cow will play in alternating turns, with Spyrosaliv playing first.

Suppose Spyrosaliv is on node $$$u$$$. Spyrosaliv has to choose any node $$$v$$$ such that the edge $$$(u, v)$$$ exists and is not blocked, and move there. If such a node doesn't exist, he loses. If $$$v = d$$$, he wins.

If it's Cow the Cow's turn, he will do these two operations in the following order:

  1. If it is not his first turn and he blocked an edge on his previous turn, unblock it.
  2. Choose an edge that he did not block in his exact previous turn and block it, or do nothing. If it's his first turn, he may block any edge.

If both Spyrosaliv and Cow the Cow play optimally, will Spyrosaliv win the game?

Input

The first line contains exactly three integers: $$$n$$$, $$$s$$$, and $$$d$$$ $$$(2 \le n \le 2 \cdot 10^5$$$, $$$1 \le s, d \le n$$$, $$$s \neq d$$$), the size of the tree, Spyrosaliv's starting node, and Spyrosaliv's destination, respectively.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, representing an edge $$$(u, v)$$$ in the tree.

The input is guaranteed to give a valid tree, and it is guaranteed that $$$s \neq d$$$.

Output

Output exactly one string: 'YES' if Spyrosaliv will win and 'NO' otherwise. Note that 'yEs', 'Yes', 'nO', and so on, are also acceptable answers.

Examples
Input
5 2 4
1 4
2 5
4 3
3 5
Output
NO
Input
2 1 2
1 2
Output
YES
Note

In the first example, the tree is as follows:

Spyrosaliv starts at node $$$2$$$, and wins if he gets to node $$$4$$$. A possible sequence of moves is as follows:

  • Spyrosaliv moves from node $$$2$$$ to $$$5$$$.
  • Cow the Cow will block edge $$$(5, 3)$$$.
  • Since Spyrosaliv can't move to node $$$3$$$, he will move back to node $$$2$$$.
  • Cow the Cow will unblock edge $$$(5, 3)$$$. Note that it is not allowed for him to block that edge again in this turn. Cow the Cow will block edge $$$(2, 5)$$$.
  • Spyrosaliv cannot make a move; therefore, he loses.

It can be shown that in this example, no matter how Spyrosaliv plays, Cow the Cow has a winning strategy.

C. Painting a Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cow the Cow has a tree of size $$$n$$$ rooted at node $$$1$$$. However, Cow the Nerd thinks that Cow the Cow's tree is boring, so he has assigned you the task of painting it.

Specifically, let your current position be $$$u$$$. In a move, you will do one of the following:

  • If $$$u$$$ is a leaf$$$^\dagger$$$ and all other nodes have been painted, then you paint $$$u$$$ and escape. Otherwise, paint $$$u$$$, choose any non-painted node, and move there.
  • If $$$u$$$ is not a leaf and all of its children have been painted, then you are trapped in the tree and fail the task. Otherwise, paint $$$u$$$ and move to any of its non-painted children.

For every node $$$u$$$ from $$$1$$$ to $$$n$$$, find out if it is possible to paint all nodes of the tree and escape successfully if you start from node $$$u$$$.

$$$^\dagger$$$A leaf of a rooted tree is a node that is not the root and has no children.

Input

The first line contains exactly one integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, ..., p_n$$$, where $$$p_i$$$ is the parent of the $$$i$$$-$$$th$$$ node.

It is guaranteed that the input provides a valid tree.

Output

Output a binary string $$$s$$$ of size $$$n$$$, where $$$s_i = 1$$$ if you can win starting from node $$$i$$$, and $$$s_i = 0$$$ otherwise.

Examples
Input
5
1 1 1 1
Output
11111
Input
2
1
Output
10
Input
6
1 1 2 3 4
Output
111000
Note

In the first example, no matter which node you start from, there's at least one possible winning sequence of moves.

In the second example, if you start from node $$$2$$$, there's only one possible sequence of moves: paint node $$$2$$$, and since it is a leaf, move to the only unpainted node, $$$1$$$. Node $$$1$$$ is not a leaf, and all of its children have been painted; therefore, you lose.

D. Cow the Tree Nerd
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A beautiful path of a weighted tree is a simple path that visits at least $$$2$$$ nodes, in which the edges it visits have alternating signs. Its cost is the sum of the weights of the edges it visits. A best path is a beautiful path with the maximum cost among all other beautiful paths in the tree.

Spyrosaliv had a weighted tree of size $$$n$$$, and he tried finding the cost of the best path. However, Cow the Cow, nerdy as he is, thought the problem was far too easy.

Therefore, he asked the following question: "In one operation, you can choose any two edges and swap their weights. What is the maximum possible cost of the best path after a finite number of such operations?"

Cow the Cow easily solved the problem, but Spyrosaliv struggled. Can you help Spyrosaliv solve this problem?

Input

The first line contains one integer, $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$.

In the $$$i$$$-$$$th$$$ of the next $$$n-1$$$ lines, there are three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(-10^9 \le w_i \le 10^9, w_i \neq 0)$$$, denoting an edge $$$(u_i, v_i)$$$ in the tree with weight $$$w_i$$$.

The input is guaranteed to provide a valid tree.

Output

Output one integer, the maximum possible cost of the best path after a finite number of swaps.

Examples
Input
6
1 2 3
2 3 -1
3 4 2
4 5 -1
4 6 -130
Output
4
Input
5
1 2 8
2 3 -1
3 4 -100
4 5 10
Output
17
Input
2
1 2 -10
Output
-10
Input
3
1 2 100
1 3 150
Output
150
Note

For the first example, see the following tree:

The path that visits nodes $$$1, 2, 3$$$ in that order is beautiful with cost $$$2$$$, but the path $$$6, 4, 5$$$ is not, since two consecutive edges have weights with the same sign.

The best path is the path that visits nodes $$$1, 2, 3, 4$$$ in that order, since it is a beautiful path with the maximal cost of $$$4$$$.

In the second example, it is optimal to swap the weights of edges $$$(3, 4)$$$ and $$$(4, 5)$$$ in one operation. Then, the cost of the best path is $$$17$$$. It can be shown that $$$17$$$ is the maximal possible cost of the best path among all possible combinations of operations.

In the third example, there is exactly one beautiful path, which visits nodes $$$1$$$ and $$$2$$$; therefore, it is the best path with cost $$$-10$$$.

E. Mirror I
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cow Meows has a tree of size $$$n$$$ rooted at node $$$1$$$ and a constant integer $$$k$$$.

However, he is over $$$10^{10^{100}}$$$ years old, and math formulas have started messing with his vision.

Specifically, he thinks that two nodes $$$a$$$ and $$$b$$$ are similar if there exists any node $$$u$$$ that is an ancestor of both $$$a$$$ and $$$b$$$, and $$$dist(a, u) \equiv dist(b, u) \equiv 0 \pmod{k}$$$, where $$$dist(u, v)$$$ represents the number of edges in the simple path from $$$u$$$ to $$$v$$$.

Your goal is to help Cow Meows count the number of pairs $$$(u, v)$$$, $$$1\leq u \lt v \leq n$$$, such that nodes $$$u$$$ and $$$v$$$ are similar.

Input

The first line contains two integers $$$n$$$ and $$$k$$$, $$$(1 \le k \le n \le 2 \cdot 10^5)$$$, the size of the tree and the constant respectively.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, ..., p_n$$$, where $$$p_i$$$ is the parent of the $$$i$$$-$$$th$$$ vertex.

It is guaranteed that the input forms a valid tree.

Output

Output exactly one integer, the number of distinct unordered pairs of similar nodes.

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

In the first example, the tree is the following:

With $$$k = 2$$$, the similar pairs are $$$(5, 2)$$$, $$$(3, 4)$$$, $$$(1, 4)$$$, $$$(1, 3)$$$.

In the final example, all nodes are similar to each other.

F. Mirror II
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of size $$$n$$$ rooted at node $$$1$$$. Each node $$$u$$$ has a value $$$val_u$$$.

Let $$$dis(u, v)$$$ be the sum of the values of the nodes in the simple path from $$$u$$$ to $$$v$$$. Also, let $$$d_u = dis(1, u)$$$. Two nodes $$$u$$$ and $$$v$$$ are considered similar if $$$(d_u + d_v)^2 = (d_u - d_v)^2 = dis(u, v)$$$.

Your goal is to find the number of pairs $$$(u,v)$$$, $$$1 \le u \lt v \le n$$$, such that nodes $$$u$$$ and $$$v$$$ are similar.

Input

The first line of the input contains one integer, $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$.

The second line of the input contains $$$n$$$ integers $$$val_1, val_2, ..., val_n$$$ $$$(-10^9 \le val_i \le 10^9)$$$, where $$$val_i$$$ is the value of the $$$i$$$-$$$th$$$ node.

The third line of the input contains $$$n-1$$$ integers $$$p_2, p_3, ..., p_n$$$ , where $$$p_i$$$ is the parent of the $$$i$$$-$$$th$$$ node.

It is guaranteed that the input forms a valid tree.

Output

Output exactly one integer, the number of pairs $$$(u,v)$$$ $$$(1 \le u \lt v \le n)$$$ such that nodes $$$u$$$ and $$$v$$$ are similar.

Examples
Input
6
0 1 0 -1 0 0
1 2 2 4 1
Output
9
Input
10
0 -7 0 5 7 0 -1 0 7 0
9 2 1 8 2 5 1 8 3
Output
10
Note

For the first example:

The pairs are $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(1, 6)$$$, $$$(2, 6)$$$, $$$(3, 6)$$$, $$$(4, 6)$$$, $$$(5, 6)$$$.

Take as an example the pair $$$(4, 6)$$$. Because $$$d_4 = 0$$$, $$$d_6 = 0$$$, and $$$dis(4, 6) = 0$$$, then $$$(d_4 + d_6)^2 = (d_4 - d_6)^2 = dis(4, 6) = 0$$$. Therefore, the nodes $$$4$$$ and $$$6$$$ are similar.

G. Crown
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$k$$$ cows playing a game, each positioned on distinct nodes of a tree of size $$$n$$$ rooted at node $$$1$$$. The $$$i$$$-$$$th$$$ cow has been assigned a value, $$$val_i$$$. Every node can be either blocked or not blocked. Initially, no node is blocked. In each second of the game, every cow chooses to make one of the following moves:

  • Stay at its current node, or
  • If it is at node $$$u$$$ and $$$p_u$$$ has not been blocked, move to $$$p_u$$$, where $$$p_u$$$ is the parent of node $$$u$$$.

If in a second every cow chooses to stay at its current node, the game ends. The last second does not count towards the total amount of seconds the game lasted. Multiple cows may be on the same node by the end of a game. The sum of a node is the sum of the values of the cows on that node when the game ends. The score of the game is the sum of the node with the maximal sum among all other nodes. After a game ends, all cows return to their starting nodes. The goal of the cows is to maximize the score of the game in as little time as possible.

However, SpyrosAliv does not like cows; therefore, he will try to ruin their game.

Specifically, there will be $$$q+1$$$ games. The first game will be played without any changes. Before the $$$i$$$-$$$th$$$ of the next $$$q$$$ games starts, SpyrosAliv will do one of the following:

  1. remove the cow from node $$$u_i$$$, or
  2. block node $$$u_i$$$ (there is no cow on that node)

Note that changes done on game $$$j$$$ are not reverted and affect all following games $$$j, j+1, ..., q, q+1$$$.

For each game, help Cow the Cow calculate the score of the game and how long it lasted if the cows played optimally.

Input

The first line of the input contains two integers, $$$n$$$ and $$$k$$$, $$$(1 \le k \le n \le 2 \cdot 10^5)$$$.

The second line of the input contains $$$k$$$ distinct integers, where the $$$i$$$-$$$th$$$ integer is the position of the $$$i$$$-$$$th$$$ cow.

The third line of the input contains $$$k$$$ integers, $$$val_1, val_2, ..., val_k$$$ $$$(1 \le val_i \le 10^9)$$$, the value of the $$$i$$$-$$$th$$$ cow.

The fourth line of the input contains $$$n-1$$$ integers $$$p_2, p_3, ..., p_n$$$, where $$$p_i$$$ $$$(1 \le p_i \le n)$$$ is the parent of the $$$i$$$-$$$th$$$ node.

The following line contains exactly one integer, $$$q$$$ $$$(0 \le q \le n)$$$, the number of queries.

The $$$i$$$-$$$th$$$ of the next $$$q$$$ lines contains two integers, $$$t_i$$$ and $$$u_i$$$ $$$(1 \le t_i \le 2, 1 \le u_i \le n)$$$, the type of the $$$i$$$-$$$th$$$ query and its node respectively. If $$$t_i = 1$$$, then SpyrosAliv removes the cow from node $$$u_i$$$. If $$$t_i = 2$$$, then SpyrosAliv blocks node $$$u_i$$$.

It is guaranteed that if $$$t_i = 1$$$, there is a cow at node $$$u_i$$$. If $$$t_i = 2$$$, $$$u_i$$$ is not blocked and has no cow.

It is guaranteed that the input provides a valid tree.

Output

Output $$$q + 1$$$ lines.

On the $$$i$$$-$$$th$$$ line, output two integers: the score of the $$$i$$$-$$$th$$$ game and the seconds it lasted if the cows played optimally.

Examples
Input
7 4
2 3 5 7
5 3 8 2
1 2 2 4 4 4
7
1 2
2 2
2 4
1 5
1 3
1 7
2 5
Output
18 2
13 2
10 1
8 0
3 0
2 0
0 0
0 0
Input
5 4
3 4 5 2
1 10 5 7
5 2 2 1
5
2 1
1 4
1 3
2 3
2 4
Output
23 2
23 2
13 2
12 1
12 1
12 1
Input
5 3
5 2 4
1891 54 5645
5 1 1 4
5
2 3
1 4
1 5
2 5
1 2
Output
7590 2
7590 2
1945 1
54 0
54 0
0 0
Note

On the first example, this is what the tree looks like before the third game:

Green nodes have a cow on them, and their label is the value of their cow. Node $$$2$$$ has been blocked. The optimal moves for the cows are the following:

  • At second $$$1$$$, cows at nodes $$$5$$$ and $$$7$$$ will move upwards to node $$$4$$$. Note that the cow at node $$$3$$$ can not make a move, since its parent has been blocked.
  • At second $$$2$$$, no cow can make a move. The game ends since no cow made a move. This second does not count towards the total seconds the game lasted.

The game has lasted $$$1$$$ second. Node $$$4$$$ has a sum of $$$10$$$, node $$$3$$$ has a sum of $$$3$$$, and all other nodes have a sum of $$$0$$$. The score of the game is the sum of node $$$4$$$, which is $$$10$$$. The cows needed $$$1$$$ second to achieve this score. It can be shown that $$$10$$$ is the maximal possible score they can achieve, and that they need at least $$$1$$$ second to achieve it.

After the game ends, all cows return to their starting nodes. That means that the image above represents the tree both before and right after the third game.