Fair - MarisaOJ: Marisa Online Judge

A fairground has the form of a regular polygon consisting of

$n$ vertices, the vertices are numbered from

$1$ to

$n$ clockwise. The organizer divides the fair area by

$n - 3$ dividing lines to obtain

$n - 2$ triangular booths, the dividing lines do not intersect inside the polygon, the dividing line

$k$ passes through two distinct vertices

$i_k,j_k$

$(1 \le k \le n - 3)$ . Thus, a booth will have three sides, each side is a polygonal edge or dividing line. To encourage visitors to visit the stalls, the organizer will give prizes worth

$t_k$ to visitors when passing through the

$k$ th dividing line. Alice plans to enter the fairground from a booth whose face is an edge connecting vertices

$u$ and vertex

$(u \\% n + 1)$ then exit the fairground from a booth whose face is an edge connecting vertices

$v$ and vertex

$(v \\% n + 1)$ . Alice hopes that each booth will be visited no more than once and the total value of the rewards received will be the greatest. Note that

$u \neq v$ and the operation

$\\%$ is to divide and receive remainder. Requirement: Alice has

$q$ assumptions, each assumption described by two integers

$u,v$ means that Alice enters from the edge connecting vertex

$u$ and vertex

$(u \\% n + 1)$ and comes out from the edge connecting vertex

$v$ and vertex

$(v \\% n + 1)$ , for each assumption, help Alice compute the maximum possible total value of the rewards that can be achieved. ### Input - The first line contains two positive integers

$n,q$

$(q \le n);$ - The

$k$ -th line

$(1 \le k \le n - 3)$ contains three positive integers

$i_k,j_k,t_k$ describing the

$k$ -th dividing line

$(1 \le i_k,j_k \le n$ and

$i_k \neq j_k;t_k \le 10^9);$ - The second line

$s$

$(1 \le s \le q)$ includes two positive integers

$u,v$ describing an assumption. ### Output - Write out

$q$ lines, each line contains an integer that is the maximum total value of the rewards that can be achieved. ### Example Input:

$6 2 2 4 1 2 5 2 2 6 3 1 5 1 2$

Output:

$3 6$

### Subtask - Subtask 1 (40%) :

$n \le 10$ - Subtask 2 (30%) :

$n \le 100$ - Subtask 3 (30%) :

$n \le 10^5$

The 2023 Youth Informatics Contest - National Preliminary Group C1
	Tree rows
	Fair
	Extreme set

The 2023 Youth Informatics Contest - National Preliminary Group C2
	Triangle
	Tree rows
	Fair

Topic

Others

Rating

1800

Source

Tin học trẻ

Solution (0)

Solution