P17450 Same Frequency Echo

You are given a weighted tree with $n$ nodes rooted at node $1$. Node $i$ has: - frequency band $c_i$; - transmission time $a_i$. Each frequency band $c$ has an importance value $w_c$. For two different nodes $u, v$ that use the same frequency band, define their **synchronization cost** as $$ D(u,v)=|a_u-a_v|+\operatorname{dist}(u,v), $$ where $\operatorname{dist}(u,v)$ is the sum of edge weights on the simple path between $u$ and $v$. Each query provides a node $x$ and a non-negative integer $K$. We say that frequency band $c$ produces an echo in the region governed by $x$ if and only if there exist two different nodes $$ u,v\in\operatorname{subtree}(x) $$ such that $$ c_u=c_v=c,\qquad D(u,v)\le K. $$ Here, $\operatorname{subtree}(x)$ denotes the subtree rooted at $x$. For each query, compute the sum of importance values of all frequency bands that produce an echo: $$ \sum_{c=1}^{m} w_c \bigl[\exists\,u\ne v\in\operatorname{subtree}(x),\ c_u=c_v=c,\ D(u,v)\le K\bigr]. $$ The square brackets denote the Iverson bracket: it equals $1$ if the condition holds, and $0$ otherwise.

The first line contains three integers $n,m,q$ ($1\le n\le 10^6$, $1\le m\le 10^5$, $1\le q\le 10^6$), representing the number of nodes, the number of frequency bands, and the number of queries, respectively. The second line contains $m$ integers $w_1,w_2,\ldots,w_m$ ($0\le w_c\le 10^9$), representing the importance value of each frequency band. The third line contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1\le c_i\le m$), representing the frequency band used by each node. The fourth line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 10^9$), representing the transmission time of each node. The next $n-1$ lines each contain three integers $u,v,d$ ($1\le u,v\le n$, $0\le d\le 10^9$), indicating an undirected edge between nodes $u$ and $v with weight $d$. The next $q$ lines each contain two integers $x,K$ ($1\le x\le n$, $0\le K\le 4\times 10^{18}$), representing one query. It is guaranteed that the edges form a tree, and that the answer fits in a signed $64$-bit integer.

For each query, output one integer per line, representing the answer.

The synchronization costs between nodes with the same frequency are as follows: - Nodes on frequency band $1$ are $1,3,6$: $D(1,3)=|10-13|+3=6$, $D(1,6)=|10-20|+5=15$, $D(3,6)=|13-20|+2=9$. - Nodes on frequency band $2$ are $2,5$: $D(2,5)=|4-9|+1=6$. - Nodes on frequency band $3$ are $4,7$: $D(4,7)=|8-7|+14=15$. Therefore: - In query $(1,5)$, no frequency band produces an echo, so the answer is $0$. - In query $(1,6)$, frequency bands $1,2$ produce echoes, so the answer is $5+7=12$. - In query $(2,6)$, only frequency band $2$ produces an echo, so the answer is $7$. - In query $(3,9)$, only frequency band $1$ produces an echo, so the answer is $5$. - In query $(1,15)$, all three frequency bands produce echoes, so the answer is $5+7+11=23$. Translated by ChatGPT 5