P15842 [Bulgarian NOI 2024] Longest Path / longest

You are given a weighted tree with $n$ vertices. Its edges are $(u_1, v_1)$ (weight $w_1$), $(u_2, v_2)$ (weight $w_2$), $\dots$, $(u_{n-1}, v_{n-1})$ (weight $w_{n-1}$). Write a program to support $q$ queries, where each query is one of the following two types: - Type 1: Given $x, k, n_1, \dots, n_k$, find the maximum path length from vertex $x$ to any vertex $y$, under the constraint that the path from $x$ to $y$ must not pass through any of the specified vertices $n_1, \dots, n_k$. - Type 2: Given $i, w$, modify the weight of the $i$-th edge $(u_i, v_i)$ to $w$.

Read an integer $n$ from the first line of standard input. The next $n - 1$ lines each contain three integers $u_i, v_i, w_i$, describing an edge connecting vertices $u_i$ and $v_i$ with weight $w_i$. The next line contains an integer $q$. Each of the following $q$ lines first gives the query type (1 or 2): - If the type is 1, then read $x$, $k$, and $k$ integers $n_1, \dots, n_k$. - If the type is 2, then read $i$ and $w$.

For each type 1 query, print the required maximum path length on a separate line to standard output.

### Sample 1 Explanation In the queries, the target vertices that need to be found are, in order, $5, 5, 5, 3, 3, 4, 4, 2$. ### Constraints - $1 \le n, q,\ \sum k \le 200000$ - $1 \le u_i, v_i \le n$ - $1 \le w, w_i \le 10^9$ - For all $1 \le i \le k$, $n_i \ne x$ - For all $1 \le i \ne j \le k$, $n_i \ne n_j$ ### Subtasks | Subtask | Points | Additional Constraints | |:------:|:----:|:------------------------:| | $1$ | $5$ | $n, q \le 5000$ | | $2$ | $15$ | The degree of each vertex is at most $2$ | | $3$ | $15$ | $k = 0$ | | $4$ | $30$ | There are no type $2$ queries | | $5$ | $35$ | None | You can obtain the points for a subtask only if you pass all testdata for that subtask. Translated by Qwen3.5-397B-A17B. Translated by ChatGPT 5