시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 4 | 2 | 2 | 50.000% |
You are given a tree with $N$ vertices. The distance between two vertices is the number of edges lying on the simple path between them.
There are $Q$ queries. Each query is specified by two vertices $u$ and $v$ and an integer $d$. A pair of vertices is called good if the distance between them is not less than $d$. In each step, you can only move between a good pair of vertices. Now your task is to calculate the minimum number of steps you have to make in order to get from $u$ to $v$. If you can not reach the destination, the answer is $-1$.
A lot of queries are given to you to make this problem difficult.
The first line of input contains three integers $N$, $Q$ and $M$: the number of vertices, the number of queries and the upper bound for $d$. ($1 \leq N \leq 2 \cdot 10^5$, $1 \leq Q \leq 10^6$, $1 \leq M \leq 2 \cdot 10^5$).
The second line contains $N - 1$ integers $f_2$, $f_3$, $\ldots$, $f_N$ which mean that, for every $i$ such that $2 \leq i \leq N$, there is an edge between vertices $i$ and $f_i$ in the tree ($1 \leq f_i < i$).
The third line contains six integers $u_1$, $v_1$, $d_1$, $A$, $B$ and $C$ ($1 \leq u_1, v_1 \leq N$, $0 \leq d_1 < M$, $10^4 \leq A, B, C \leq 2 \cdot 10^4$).
The first query is specified by $u_1$, $v_1$ and $d_1$.
The $i$-th ($2 \leq i \leq Q$) query is specified by $u_i$, $v_i$ and $d_i$ which are generated by the following rules:
Here, $\mathit{ans}_{k}$ is the answer for query $k$.
Output the integer $$S = \sum\limits_{i = 1}^{Q} i \cdot (\mathit{ans}_i + 1)\text{.}$$
6 9 5 1 2 1 3 3 6 3 0 10865 16947 15183
55