F. 1-1-1, бесплатное дерево!
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Каждая вершина имеет начальный цвет $$$a_i$$$.

Каждое ребро дерева задаётся тремя числами: $$$u_i$$$, $$$v_i$$$ и $$$c_i$$$, где $$$u_i$$$ и $$$v_i$$$ — концы ребра, а $$$c_i$$$ — параметр ребра. Стоимость ребра определяется следующим образом: если цвета вершин $$$u_i$$$ и $$$v_i$$$ совпадают, стоимость равна $$$0$$$, иначе стоимость равна $$$c_i$$$.

Также вам дано $$$q$$$ запросов. Каждый запрос имеет вид: перекрасить вершину $$$v$$$ в цвет $$$x$$$. Запросы зависят друг от друга (после каждого запроса изменение цвета сохраняется). После каждого запроса необходимо вывести сумму стоимостей всех рёбер дерева.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2\cdot10^5$$$)— количество вершин и количество запросов соответственно.

Во второй строке содержится $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$i$$$-е число задаёт начальный цвет вершины $$$i$$$.

В следующих $$$n-1$$$ строках описаны рёбра дерева. Каждая строка содержит три целых числа $$$u$$$, $$$v$$$ и $$$c$$$, обозначающих ребро между вершинами $$$u$$$ и $$$v$$$ с параметром $$$c$$$ ($$$1 \le u, v \le n$$$, $$$1 \le c \le 10^9$$$).

В следующих $$$q$$$ строках записаны запросы. Каждый запрос содержит два целых числа $$$v$$$ и $$$x$$$ — перекрасить вершину $$$v$$$ в цвет $$$x$$$ ($$$1 \le v,x \le n$$$).

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам данных не превосходят $$$2\cdot10^5$$$

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число — сумму стоимостей всех рёбер дерева после применения соответствующего запроса.

Пример
Входные данные
4
1 1
1
1 1
2 3
1 1
1 2 10
1 2
2 2
1 1
5 4
1 2 1 2 3
1 2 5
2 3 3
2 4 4
4 5 7
3 2
5 2
1 2
2 3
4 3
1 1 2 2
1 2 2
2 3 6
2 4 8
3 1
4 1
2 2
Выходные данные
0
10
0
10
12
5
0
12
8
0
16
Примечание

Первый пример: $$$n =1$$$, одна вершина — нет рёбер. Запрос: перекрасить $$$a_1$$$ в $$$1$$$, сумма стоимостей равна $$$0$$$.

Второй пример: $$$n=2$$$, ребро $$$1 - 2$$$ ($$$c=10$$$). Запросы:

  • $$$a_1 = 2$$$: цвета [$$$2, 1$$$], стоимость равна $$$10$$$;
  • $$$a_2 = 2$$$: цвета [$$$2, 2$$$], стоимость $$$0$$$;
  • $$$a_1 = 1$$$: цвета [$$$1, 2$$$], стоимость $$$10$$$.

Третий пример. $$$n=5$$$, рёбра: $$$1 - 2\ (c=5)$$$, $$$2 - 3\ (c=3)$$$, $$$2 - 4\ (c=4)$$$, $$$4 - 5\ (c=7)$$$. Начальные цвета $$$[1,2,1,2,3]$$$. Запросы:

$$$a_3 = 2 \rightarrow [1,2,2,2,3]$$$: рёбра $$$1 - 2\ (c = 5)$$$ и $$$4 - 5\ (c=7)$$$ дают $$$12$$$;

$$$a_5 = 2 \rightarrow [1,2,2,2,2]$$$: ребро $$$1 - 2\ (c=5)$$$, стоимость $$$5$$$;

$$$a_1 = 2 \rightarrow [2,2,2,2,2]$$$: стоимость равна $$$0$$$;

$$$a_2 = 3 \rightarrow [2,3,2,2,2]$$$: рёбра $$$1-2\ (5)$$$, $$$2-3\ (3)$$$, $$$2-4\ (4)$$$ дают $$$12$$$.