Shuffled Tree - ReimuOJ: Reimu Online Judge

Given a tree

T

$T$ with

n

$n$ vertices and

n - 1

$n-1$ weighted edges, initially, vertex

i

$i$ is assigned color

i

$i$ for

1 \leq i \leq n

$1 \leq i \leq n$ . Since Marisa is dissatisfied with the structure of the tree

T

$T$ , she decides to shuffle the tree

T

$T$ to obtain a new tree

T^{'}

$T'$ , where vertex

i

$i$ will have the color

p_{i}

$p_i$ (

1 \leq i \leq n

$1 \leq i \leq n$ ), and

p_{1}, p_{2}, \dots, p_{n}

$p_1, p_2, \ldots, p_n$ is a permutation of

1, 2, \dots, n

$1, 2, \ldots, n$ . After shuffling the tree

T

$T$ , Marisa provides

q

$q$ queries. Each query

i

$i$ consists of

u_{i}, v_{i}, x_{i}

$u_i, v_i, x_i$ . For the simple path from

u_{i}

$u_i$ to

v_{i}

$v_i$ in tree

T

$T$ , let the set of distinct colors on this path be

s_{1}, s_{2}, \dots, s_{k}

$s_1, s_2, \ldots, s_k$ . Compute the total distance from

x_{i}

$x_i$ to every vertex with color

s_{j}

$s_j$ in tree

T^{'}

$T'$ , for all

1 \leq j \leq k

$1 \leq j \leq k$ . ### Input - The first line contains two positive integers

n

$n$ and

q

$q$ . - The second line contains

n

$n$ positive integers

p_{1}, p_{2}, \dots, p_{n}

$p_1, p_2, \ldots, p_n$ . - The next

n - 1

$n-1$ lines, the

i

$i$ -th line contains three positive integers

u_{i}, v_{i}, w_{i}

$u_i, v_i, w_i$ , describing an edge of the tree with weight

w_{i}

$w_i$ . - The next

q

$q$ lines, the

i

$i$ -th line contains three positive integers

u_{i}, v_{i}, x_{i}

$u_i, v_i, x_i$ . ### Output - Print

q

$q$ lines, each containing the answer to the corresponding query. ### Constraints -

1 \leq n, q \leq 10^{5} .

$1 \le n,q \le 10^5.$ -

w_{i} \leq 10^{3} .

$w_i \le 10^3.$ ### Example Input

5253214121231242152341515

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

Output

57

$5 7$

Centroid Decomposition
	Short paths
	Colorful path
	Radius
	Shuffled Tree
	Marisa go shopping 2

Topic

Tree

Data structure

Rating

2400

Source

MarisaOJ Original

Solution (0)

Solution