P4866 Zrz_orz Loves Secondary Element

zrz_orz really loves anime (èr cì yuán)!!

As everyone knows, zrz_orz is the strongest hardcore otaku in the whole computer room. ~~He even used “talk-no-jutsu” to make Samcompu put Kurumi Tokisaki on his website~~. (But it seems Samcompu realized something and removed Kurumi again.) As a member of the new generation of otaku, from desktop wallpapers to input method skins, everything is filled with anime traces. So, he often dreams of some anime characters. zrz_orz’s dream is a connected graph with $n$ nodes and $n-1$ edges. There are $m$ nodes that have an anime character on them. For zrz_orz, each anime character has a corresponding $pos_i$ and $val_i$, meaning which node this character is on, and how much happiness value zrz_orz gains by chatting with them. (For some reason, the chatting process does not need to be counted in time.) Unfortunately, each time zrz_orz dreams, he only has $tim_i$ units of time. Now please tell him: in each dream, what is the maximum happiness value he can obtain? Notes: 1. Each time zrz_orz dreams, he will always start from node $1$. 2. After each dream, the graph in zrz_orz’s dream will not change. 3. **After each dream, zrz_orz must return to node $\bm1$, otherwise he will get lost in the dream!**

The first line contains three positive integers $N, M, T$, representing the number of nodes in the graph, the number of anime characters, and the number of days of dreaming. The next $N-1$ lines each contain three positive integers $u_i, v_i, w_i$, representing that the $i$-th edge connects two nodes, and the time cost for zrz_orz to traverse this edge. The next $M$ lines each contain two positive integers $pos_j$ and $val_j$, representing the position of the $j$-th anime character and the happiness value it can bring to zrz_orz. The next $T$ lines each contain one positive integer $tim_k$, representing the dreaming time on the $k$-th day.

Output a total of $T$ lines. Each line contains one positive integer, representing the maximum happiness value zrz_orz can obtain on that day.

 On the first day, he cannot go anywhere. On the second day, taking the route $1\to3\to6\to7\to6\to3\to1$, the maximum happiness value is $7$. On the third day, he can traverse all places once. - Subtask 1 (20 pts): $1 \leqslant T \leqslant 10$, $1 \leqslant N \leqslant 1000$, $1 \leqslant M \leqslant 20$, $1 \leqslant tim_k \leqslant 1000$. - Subtask 2 (40 pts): $1 \leqslant T \leqslant 10^5$, $1 \leqslant N \leqslant 10^5$, $1 \leqslant M \leqslant 20$, $1 \leqslant tim_k \leqslant 10^5$. - Subtask 3 (40 pts): $1 \leqslant T \leqslant 5\times10^4$, $1 \leqslant N \leqslant 5000$, $1 \leqslant M \leqslant 100$, $1 \leqslant tim_k \leqslant 100$, $1 \leqslant w_i \leqslant 5$. For all test points: $1 \leqslant pos_j, u_i, v_i \leqslant N$, $1 \leqslant \sum val_j \leqslant 2\times10^9$, $1 \leqslant w_i \leqslant 20$, $1 \leqslant tim_k \leqslant 10^5$. Note: The marked score is the score of this Subtask. Each Subtask must be completely correct to get the score. The time limit for Subtask 2 is 1.5 s. $$ \color{white} \text{NOIP 2合1} $$ Translated by ChatGPT 5