We have $$$n$$$ squares, $$$s_1, s_2, \dots, s_n$$$, on a 2D plane. Now, we want to draw a square $$$S$$$ such that for each of the existing squares, the intersection with $$$S$$$ is also a square with nonzero area.
Formally, we want to find a new square $$$S$$$ such that for each $$$i \in \{1, 2, \dots, n\}$$$, the intersection $$$S \cap s_i$$$ is also a square with nonzero area.
Print out any valid square $$$S$$$.
The first line contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of squares laid out.
Each of the next $$$n$$$ lines describes a square using four integers $$$x_1, y_1, x_2, y_2$$$, where $$$(x_1, y_1)$$$ is the lower-left corner and $$$(x_2, y_2)$$$ is the upper-right corner. It is guaranteed that $$$x_1 \lt x_2$$$, $$$y_1 \lt y_2$$$, and that the shape described is an axis-aligned square. All coordinates lie within the range $$$[-10^9, 10^9]$$$.
Output the square $$$S$$$ as four integers $$$x_1, y_1, x_2, y_2$$$, denoting its lower-left and upper-right corners. It must satisfy $$$x_1 \lt x_2$$$ and $$$y_1 \lt y_2$$$, and all coordinates must lie within the range $$$[-10^9, 10^9]$$$. The square must be axis-aligned.
3 2 3 4 5 7 3 10 6 8 1 12 5
3 4 9 10
1 1 1 2 2
1 1 2 2
Below is an illustration of the sample test case, where the blue squares are the ones given in the input and the red square is our output.
—
Problem Idea: Alex_C
Problem Preparation: eysbutno
Occurrences: Novice A / Advanced A
Determine the maximum possible width of any possible binary tree constructed with $$$n$$$ nodes.
- A binary tree is defined as any tree where all nodes have at most 2 children.
- The width of a tree is defined as the maximum number of nodes at any level of the tree. Null nodes do not contribute to the width of the tree.
The first line of input will contain an integer $$$t$$$ ($$$1 \leq t \leq 2 \times 10^5$$$), indicating that there are $$$t$$$ test cases. The next $$$t$$$ lines will each contain an integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the input for each test case.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-6$$$ satisfy $$$1 \leq n \leq 10^5$$$.
Tests $$$7-20$$$ satisfy no additional constraints.
Output one integer on a separate line per test case, the maximum possible width of any binary tree constructed with $$$n$$$ nodes.
341017
2 4 8
Problem Idea: Mustela_Erminea
Problem Preparation: Mustela_Erminea
Occurrences: Novice G / Advanced B
You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$.
Define $$$f(k)$$$ as the $$$\text{MEX}$$$ of the maximum value of all subarrays of length $$$k$$$.
Print $$$f(k)$$$ for each $$$k$$$ from 1 to n.
More formally, output the values of $$$\text{MEX}^{n-i}_{j=0} \max^{i}_{k=1} a_{j+k}$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$.
A subarray of length $$$k$$$ is an array that contains exactly $$$k$$$ elements obtained by removing a prefix and a suffix from the original array.
The $$$\text{MEX}$$$, or minimal excluded, of a sequence is the smallest non-negative integer not present in that sequence.
The first line contains $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of elements in the array $$$a$$$.
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-6$$$ satisfy $$$n \leq 10^3$$$.
Tests $$$7-8$$$ satisfy $$$a_i=i-1$$$.
Tests $$$9-20$$$ satisfy no additional constraints.
One line containing $$$n$$$ integers, the $$$i$$$-th integer denoting the value of $$$\text{MEX}^{n-i}_{j=0} \max^{i}_{k=1} a_{j+k}$$$ at $$$i$$$.
32 1 0
3 0 0
For $$$k=1$$$, the $$$\max$$$ of each subarray is $$${2, 1, 0}$$$, so the $$$\text{MEX}$$$ is $$$3$$$.
For $$$k=2$$$, the $$$\max$$$ of each subarray isare $$${2, 1}$$$, so the $$$\text{MEX}$$$ is $$$0$$$.
For $$$k=3$$$, the $$$\max$$$ of each subarray isare $$${2}$$$, so the $$$\text{MEX}$$$ is $$$0$$$.
—
Problem Idea: culver0412
Problem Preparation: Jasonwei08
Occurrences: Novice H / Advanced C
Mr. G's students are hanging up pennants! There is a wall with $$$L$$$ slots, and has $$$N$$$ pennants hung on slots $$$1$$$ through $$$N$$$. The pennant in the $$$i$$$-th slot has rank $$$r_i$$$ (not necessarily distinct), and the pennants are ordered by rank, so $$$r_i\le r_{i+1}$$$ for $$$1\le i \lt N$$$. In one second, the students can either take a pennant off of a slot, or put a pennant of any rank onto the wall in any slot.
The students have put up all the pennants already, if they find $$$a$$$ extra pennants of rank $$$k$$$, then they must rearrange the pennants such that every pennant is on the wall, and the pennants are ordered by rank. It is guaranteed that this is always possible in finite time.
Mr. G has $$$q$$$ queries of $$$(a,k)$$$, and wants to find out the minimum time the students will take for each combination of $$$(a,k)$$$. Note that the pennants are not actually rearranged, that is, the queries are independent of each other.
note: the above image is not intended to be an accurate representation of the problem.
The first line of input contains three integers $$$N$$$, $$$Q$$$, and $$$L$$$ ($$$1\le N, Q\le 2\cdot 10^5$$$, $$$N\le L\le 10^9$$$).
The following line contains $$$N$$$ integers $$$r_1, \dots, r_N$$$, ($$$1\le r_i\le N$$$). It is guaranteed that $$$r_i\le r_{i+1}$$$ for $$$1\le i \lt N$$$.
The following $$$q$$$ lines contain two integers $$$a$$$, $$$k$$$, which denote the number and rank of the newly found pennants for each query ($$$1\le a \le L-N$$$, $$$1\le k\le N$$$).
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-3$$$ satisfy $$$N, Q\le 200$$$.
Tests $$$4-20$$$ satisfy no additional constraints.
Output $$$Q$$$ lines, the $$$i$$$-th line containing a single integer, the minimum time (in seconds) the students will take for the $$$i$$$-th query.
5 5 101 3 4 5 52 15 44 24 35 1
10 9 12 10 13
In the first query, it is optimal for the students to take off the last 4 pennants, and then put up the 6 pennants (including the new ones) in order.
—
Problem Idea: jay_jayjay
Problem Preparation: jay_jayjay
Occurrences: Novice I / Advanced D
Alter's friends are playing a game of castlefall! The game has $$$N$$$ players, labelled $$$1$$$ through $$$N$$$, and $$$M$$$ words, labeled $$$1$$$ through $$$M$$$. Each player is assigned to exactly one of two non-empty teams of possibly different sizes, and each team is given one of the $$$M$$$ words. Note that the two teams are given different words.
Since players do not know which team they are on, each player has announced a clue. Specifically, the $$$i$$$-th player has a word in the set $$$S_i$$$.
Since Alter doesn't want to think, he asks you to help him answer the following question: Is it possible to uniquely determine the teams and the words corresponding to each team? If so, Alter will also ask you what the words are.
The first line contains $$$T$$$ ($$$1\le T\le 20$$$), the number of independent test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1\le N \le 20$$$, $$$1 \le M\le 10^5$$$).
In the following $$$N$$$ lines, the $$$i$$$-th line contains a binary string $$$s_i$$$ of length $$$M$$$. If the $$$j$$$-th character of $$$s_i$$$ is $$$1$$$, then the $$$i$$$-th player can possibly have the $$$j$$$-th word, that is, $$$j$$$ is in the set $$$S_i$$$. Otherwise, it is not possible for the $$$i$$$-th player to have the $$$j$$$-th word, or equivalently, $$$j$$$ is not in the set $$$S_i$$$.
It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy $$$N\le 10$$$, $$$M\le 10^3$$$.
Tests $$$3-8$$$ satisfy $$$N\le 10$$$.
Tests $$$9-20$$$ satisfy no additional constraints.
For each test case, output a single line with "Yes" if it is possible to uniquely determine both the teams and the words corresponding to each team, or "No" otherwise. If the output is Yes, output a second line with two integers, corresponding to the words given to the two teams, in increasing order.
33 40010011001103 40010000101103 4000111001001
No Yes 3 4 No
In the first sample test case, here are some possible teams:
- The first two players are on a team with word 3, and the third player is on a team with word 2.
- The first player is on a team with word 3 and the second and third players are on a team with word 2.
Since there is not a unique team, the answer is No.
In the second test case, the unique team combination is: The first and third players are on a team with word 3, and the second player is on a team with word 4.
—
Problem Idea: jay_jayjay
Problem Preparation: jay_jayjay
Occurrences: Novice J / Advanced E
You are given a connected weighted graph with $$$n$$$ vertices and $$$m$$$ bidirectional edges. You are to traverse from vertex $$$s$$$ to vertex $$$t$$$.
Across all (not necessarily simple) paths from $$$s$$$ to $$$t$$$, count the number of distinct sums of weights along those paths modulo $$$k$$$.
The first line contains the number of test cases $$$T$$$ ($$$1\leq T \leq 10$$$). The description of the test cases follows.
The first line of each test case contains five space-separated integers, $$$n$$$, $$$m$$$, $$$k$$$, $$$s$$$, and $$$t$$$ ($$$1 \leq n \leq 10^5, n-1 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$, $$$1 \leq s, t \leq n$$$).
The next $$$m$$$ lines of each test case contain three space-separated integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n, 0 \leq w \leq 10^9$$$), denoting that an edge of weight $$$w$$$ connects vertices $$$u$$$ and $$$v$$$.
It is guaranteed that the given graph is connected.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-6$$$ satisfy $$$k \leq 10$$$.
Tests $$$7-20$$$ satisfy no additional constraints.
Output one integer $$$-$$$ the number of possible sums of weights modulo $$$k$$$.
14 5 3 1 41 4 31 2 12 4 22 3 43 4 5
3
In the first test case of the sample, $$$k = 3$$$.
The path $$$1 \rightarrow 4$$$ has a sum of weights $$$3 \equiv 0 \mod 3$$$.
The path $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$$ has a sum of weights $$$10 \equiv 1 \mod 3$$$.
The path $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4$$$ has a sum of weights $$$5 \equiv 2 \mod 3$$$.
It can be shown that no other distinct sums of weights modulo $$$3$$$ can be achieved.
—
Problem Idea: culver0412
Problem Preparation: Ryan Fu
Occurrences: Novice K / Advanced F
Bessie wants to fly an airplane to escape from Farmer Nhoj's barn to Farmer John's barn! Unfortunately for Bessie, Farmer John and Farmer Nhoj are enemies, so there are no flight paths between Farmer John's barns and Farmer Nhoj's barns.
Here, the earth is a (flat) 2-d infinite Cartesian grid. There are $$$2n$$$ barns, denoted $$$1, 2, \dots, 2n$$$, each of which is located at $$$(x_i, y_i)$$$. Farmer John owns the first $$$n$$$ barns, and Farmer Nhoj owns the next $$$n$$$ barns. Also, there are $$$m$$$ bidirectional flight paths, each of which connects cities $$$u_i$$$ and $$$v_i$$$, and costs $$$e_i$$$ energy to fly through. Each farmer ensures that their barns are connected by flight paths, but since the two farmers are enemies, it is guaranteed that there are no flights between Farmer John's barns and Farmer Nhoj's barns.
Bessie wants to fly from Farmer Nhoj's barn $$$2n$$$ to Farmer John's barn $$$1$$$. Since it is not possible for Bessie to get there, Bessie must quantum tunnel once between two cities, which takes energy given by the Manhattan metric, $$$d((x_1,y_1), (x_2,y_2)) = |x_1-x_2|+|y_1-y_2|$$$.
What is the minimum energy needed for Bessie to fly from barn $$$2n$$$ to barn $$$1$$$?
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n \le 10^5$$$, $$$2(n-1)\le m\le 3\cdot 10^5$$$).
The following $$$2n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$, denoting the x and y coordinates of each of the barns ($$$1 \le x_i, y_i \le 10^9$$$). It is guaranteed that no two airports are in the same location.
Each of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$e_i$$$, denoting a flight path from $$$u_i$$$ to $$$v_i$$$, which takes energy $$$e_i$$$ ($$$1 \le e_i \le 10^9$$$).
It is guaranteed that $$$u_i \ne v_i$$$ and also that each unordered pair $$$(u, v)$$$ is present only once (that is, there are no multiple edges).
All flight paths are bidirectional. It is guaranteed that $$$u_i \le n$$$ if and only if $$$v_i \le n$$$. It is also guaranteed that the barns $$$1, 2, \dots, n$$$ are connected, and that the barns $$$n+1, n+2, \dots, 2n$$$ are also connected.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-3$$$ satisfy $$$1\le n \le 2000$$$, $$$2(n-1)\le m\le 5000$$$.
Tests $$$4-20$$$ satisfy no additional constraints.
Output a single number, the minimum energy for Bessie to fly from barn $$$2n$$$ to barn $$$1$$$.
3 61 21 13 13 22 22 12 1 22 3 21 3 36 5 25 4 16 4 1
2
In the sample test case, it is optimal for Bessie to quantum tunnel directly from node 1 to node 6, with cost $$$|2-1| + |1-2| = 2$$$.
—
Problem Idea: jay_jayjay
Problem Preparation: jay_jayjay
Occurrences: Advanced G
Given a 2D grid with obstacles, you want to move a robot to point $$$B$$$. To do this, you can summon robots at spawn points marked as $$$A$$$. (As long as it isn't obstructed)
You may also instruct robots to move. A robot can move into an adjacent cell if there is empty space in that cell. However, if there is an obstacle, the movement will be unsuccessful. If there is a robot, the robot is able to push it, as long as the cell it is pushed to is empty. If there is another robot or an obstacle, the movement is unsuccessful. The outside of the grid is made of obstacles, so robots may not move outside the grid.
After a robot is instructed to move, even if the move was unsuccessful, the robot will self destruct and cease to exist, leaving an unoccupied cell. A pushed robot does not self destruct.
Here are $$$5$$$ examples of what happens when the red robot moves to the right:
Your goal is to find the minimum number of robots you need to summon in order to move a robot to point $$$B$$$ (Moving a robot to point $$$B$$$ only for it to immediately self destruct does not count).
If it is impossible to move a robot to point $$$B$$$, print $$$-1$$$.
Additionally, it is guaranteed by the test data that if it is possible to move a robot to point $$$B$$$, it can be done so in at most $$$4 \cdot 10^{18}$$$ summoned robots.
The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 3$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$).
The next $$$n$$$ lines of each test case contain $$$m$$$ characters, representing the 2D grid.
If a character on a line is '.', the corresponding cell is empty. If it is '#', the cell is an obstacle. If it is 'A', the cell is a robot spawn point. If it is 'B', the cell is the target destination of the robots.
Once again, the test data guarantees that if it is possible to move a robot to point $$$B$$$, it can be done so in at most $$$4 \cdot 10^{18}$$$ summoned robots.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies that there is exactly one 'A' cell.
Tests $$$2-3$$$ satisfy $$$n = 1$$$.
Tests $$$4-10$$$ satisfy $$$n, m \leq 50$$$.
Tests $$$11-20$$$ satisfy no additional constraints.
Print one integer, the minimum number of robots you need to summon in order to move a robot to point $$$B$$$, or $$$-1$$$ if it is impossible.
33 3AA.AA.##B5 5AA...A.##..AAAAA..###.B.#6 6AA....AA...........................B
4 -1 64
For the first testcase of the sample, $$$4$$$ robots are required to push one to $$$B$$$. Here is a visualization:
—
Problem Idea: Alex_C
Problem Preparation: HaccerKat
Occurrences: Novice L / Advanced H
Yam told Alter about the following problem:
You are given an array of $$$n$$$ elements, $$$a_1, a_1, \dots, a_n$$$. You can perform the following 2 operations any number of times in any order:
- Remove the last element of the array. This operation can only be performed if the array is nonempty after the operation.
- Add any number to the end of the array.
You want to minimize the number of operations of type (2) performed in order to turn the array into a permutation. We define this number to be the value of an array.
Now, Yam gives Alter $$$q$$$ queries, asking for the value of a subarray. Since Alter can only process one query at a time, he asks you to solve the problem.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).
The following line contains $$$n$$$ integers, the $$$i$$$-th of which is $$$a_i$$$ ($$$1\le a_i \le 10^9$$$).
The next $$$q$$$ lines contain two integers $$$l$$$, $$$r$$$, which describe the left and right endpoints (inclusive) of the queries ($$$1\le l \le r \le n$$$).
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfy $$$n, q\le 1000$$$.
Tests $$$3-8$$$ guarantee that all $$$a_i$$$ are distinct.
Tests $$$9-12$$$ satisfy no additional constraints.
For each query, output a single integer — the value of the subarray.
5 34 5 6 2 13 52 43 4
3 3 4
5 33 8 4 2 42 53 41 4
5 2 2
In the first sample test case:
The first query asks for the answer to the array $$$[6, 2, 1]$$$. One way to achieve the minimum number of type (2) operations is:
- Add the element $$$3$$$. The array is now $$$[6, 2, 1, 3]$$$
- Add the element $$$5$$$. The array is now $$$[6, 2, 1, 3, 5]$$$.
- Add the element $$$4$$$. The array is now $$$[6, 2, 1, 3, 5, 4]$$$.
The first sample test case satisfies the conditions of tests $$$3-8$$$.
—
Problem Idea: jay_jayjay
Problem Preparation: jay_jayjay
Occurrences: Advanced I
$$$N$$$ piles of stones appeared in your house, and you need to get rid of as many of them as possible. In the $$$i$$$-th pile, there are $$$b_i$$$ black and $$$w_i$$$ white stones.
You may perform the following operations:
- Remove a black stone from a pile. All other piles gain a white stone.
- Remove a white stone from a pile. All other piles gain a black stone.
- Add a black stone to a pile. All other piles lose a white stone.
- Add a white stone to a pile. All other piles lose a black stone.
What is the minimum total number of stones you can have after performing these operations?
Each test contains multiple test cases. The first line contains the number of test cases $$$T (1 \leq T \leq 10)$$$, the number of test cases. The description of the test cases follows.
The first line of each test case contains one integer $$$N$$$, $$$(3 \leq N \leq 10^5)$$$ - the number of piles.
The second line of each test case contains $$$N$$$ integers $$$b_1 \dots b_N$$$, $$$(0 \leq b_i \leq 10^9)$$$ - the number of black stones in each pile.
The third line of each test case contains $$$N$$$ integers $$$w_1 \dots w_N$$$, $$$(0 \leq w_i \leq 10^9)$$$ - the number of white stones in each pile.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1-2$$$ satisfy $$$b_1 + b_2 \dots b_N + w_1 + w_2 \dots w_N \leq N-2$$$.
Tests $$$3-7$$$ satisfy $$$b_i = w_i$$$
Tests $$$8-14$$$ satisfy $$$n \leq 10^3, b_i \leq 10^3, w_i \leq 10^3$$$
Tests $$$15-20$$$ satisfy no additional constraints.
For each test case, on a new line, output the minimum number of stones you can have after performing the operations.
431 1 00 0 044 0 0 04 0 0 051 2 4 3 14 2 3 5 150 0 2 1 11 1 2 0 0
1 4 8 5
Problem Idea: Alex_C
Problem Preparation: Alex_C
Occurrences: Advanced J
You see the following problem in the TC University entrance exam:
Given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,...,a_n$$$, find the number of pairs of indices $$$(l,r)$$$ such that $$$1\le l\le r\le n$$$ and $$$$$$\max_{l\le i\le r} a_i+\min_{l\le i\le r} a_i=a_l+a_r.$$$$$$
Please solve it.
The first line consists of an integer, $$$n$$$ ($$$1\le n\le 5\times 10^5$$$).
The second line consists of $$$n$$$ integers, $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$).
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$n=1000$$$.
Tests $$$2-6$$$ satisfy $$$n\le 5\times 10^4$$$.
Tests $$$7-12$$$ satisfy $$$n\le 1\times 10^5$$$.
Tests $$$13-20$$$ satisfy no additional constraints.
Output an integer, the number of pairs of indices $$$(l,r)$$$ such that $$$1\le l\le r\le n$$$ and $$$$$$\max_{l\le i\le r} a_i+\min_{l\le i\le r} a_i=a_l+a_r.$$$$$$
8 1 4 2 2 5 3 1 7
21
All such pairs $$$(l,r)$$$ are $$$$$$(1,1),(1,2),(1,5),(1,8),(2,2),$$$$$$ $$$$$$(2,3),(2,4),(2,6),(3,3),(3,4),$$$$$$ $$$$$$(3,5),(4,4),(4,5),(5,5),(5,6),$$$$$$ $$$$$$(5,7),(6,6),(6,7),(7,7),(7,8),(8,8).$$$$$$
—
Problem Idea: culver0412
Problem Preparation: culver0412
Occurrences: Advanced K
Given a tree $$$T$$$ with $$$n$$$ vertices, color each edge of the tree either white or black. A path in the tree is defined as a sequence of vertices $$$v_1, v_2, \ldots, v_k$$$ such that there exists a sequence of edges connecting each consecutive pair of vertices $$$(v_i, v_{i+1})$$$ for $$$1 \leq i \lt k$$$.
A path is considered to be cool if no two edges that share an endpoint also share the same color. Additionally, a path of one vertex, and hence no edges, is also considered a cool path. Find the maximum possible number of cool paths over all possible colorings of the edges.
The first line consists of an integer $$$n\ (1\le n\leq 4\cdot 10^6)$$$, the number of vertices in the tree.
The next $$$n-1$$$ lines contain two integers $$$s_i,t_i\ (1\leq s_i\ne t_i\leq n)$$$, denoting the $$$i$$$-th edge in the tree.
It is guaranteed that the given edges form a tree.
–
Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.
Tests $$$1-2$$$ satisfy $$$n \leq 100$$$.
Tests $$$3-7$$$ satisfy $$$n \leq 1000$$$.
Tests $$$8-12$$$ satisfy $$$n \leq 2\cdot 10^4$$$.
Tests $$$13-15$$$ satisfy $$$n \leq 10^5$$$.
Tests $$$16-22$$$ satisfy $$$n \leq 10^6$$$.
Tests $$$23-25$$$ satisfy no additional constraints.
Output an integer, the maximum possible number of cool paths over all possible colorings of the edges.
31 32 1
6
51 34 23 53 2
14
For the first sample test case, color edge $$$1-3$$$ white and edge $$$2-1$$$ black. Then the paths $$$1,2,3,1-2,1-3,2-1-3$$$ are all cool.
For the second sample test case, color edges $$$1-3,3-5,4-2$$$ black and $$$3-2$$$ white. Then the paths $$$1,2,3,4,5,1-3,2-3,2-4,3-5,1-3-2,2-3-5,3-2-4,1-3-2-4,4-2-3-5$$$.
—
Problem Idea: culver0412
Problem Preparation: culver0412
Occurrences: Advanced L