#P6162. 「THUPC 2019」不用找的树

    ID: 5452 传统题 10000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>数据结构图论CF3300分块树形DP分治树的重心

「THUPC 2019」不用找的树

「THUPC 2019」不用找的树

题目描述

给出一棵 nn 个节点的树,结点标号从 11 到 nn。

定义树上两点 a,ba,b 间的距离 d(a,b)d\left( a,b\right) 是最小的非负整数 kk,满足存在结点序列 v0,v1,…,vkv_0,v_1,\dots ,v_k,满足 v0=av_0=a,vk=bv_k=b,且对于 0≤i≤k−10\leq i\leq k-1 有 viv_i 和 vi+1v_{i+1} 之间在树上有一条边相连。

有 mm 个询问,每个询问包含参数 p0,d0,p1,d1p_0,d_0,p_1,d_1,求:

$$\sum\limits_{d\left(p_0,a\right)\leq d_0} {\sum\limits_{d\left(p_1,b\right)\leq d_1} {d(a,b)}}$$

分别令 A={a∣d(p0,a)≤d0}A=\{a\mid d(p_0,a)\le d_0\}、B={b∣d(p1,b)≤d1}B=\{b\mid d(p_1,b)\le d_1\}。统计的是笛卡尔积 A×BA\times B 中的有序点对;两集合可以重叠,允许 a=ba=b,此时贡献为 00。答案不取模。

输入格式

第一行一个整数 nn,表示树的节点数目。

接下来一行 n−1n-1 个整数 f2,f3,…,fnf_2 ,f_3 ,\dots, f_n,依次表示 ii 和 fif_i(1≤fi≤i−11\leq f_i\leq i-1)之间有一条边。

接下来一行一个整数 mm,表示询问数目。

接下来 mm 行依次描述所有询问:每行四个整数 p0,d0,p1,d1p_0,d_0,p_1,d_1(1≤p0,p1≤n1\leq p_0 ,p_1\leq n,0≤d0,d1≤n−10\leq d_0 ,d_1\leq n-1)描述一组询问。

保证 1≤n≤1051\leq n\leq 10^5,1≤m≤1051\leq m\leq 10^5。

输出格式

共 mm 行,依次回答各组询问:每行输出一个整数表示这组询问的答案。

样例输入 1

7
1 1 2 3 5 2
5
5 1 5 0
2 0 5 0
2 2 4 5
7 2 2 4
3 2 5 4

样例输出 1

2
3
69
57
70