#P4448. [Scoi2015]情报传递

    ID: 3653 传统题 1000ms 512MiB 尝试: 1297 已通过: 495 难度: 6 上传者: 标签>难度分类提高离线与分治离线查询查询排序树算法子树转区间数据结构差分树状数组LCA树上倍增CF2100

[Scoi2015]情报传递

[SCOI 2015] 情报传递

题目描述

nn 名情报员组成一棵树。除一名首领外,每人有且只有一名直属上线,彼此只能沿这棵树的边联系。公司每天恰好派发一个任务。

  • 搜集情报:指派一名情报员开始搜集。所有人的危险值最初都是 00。若某人从第 tt 天开始搜集情报,则第 tt 天危险值仍是 00,之后每天增加 11;没有开始搜集的人危险值一直为 00。
  • 传递情报:从情报员 XX 向情报员 YY 传递,参与者是两人之间唯一简单路径上的所有情报员,包括两端。当天危险值严格大于风险控制值 CC 的参与者构成威胁。传递本身不改变危险值。

对每个传递任务,求参与者总数以及其中构成威胁的人数。

输入格式

第一行一个整数 nn(1≤n≤2×1051\le n\le2\times10^5)。

第二行 nn 个整数 P1,…,PnP_1,\ldots,P_n(0≤Pi≤n0\le P_i\le n)。若 Pi=0P_i=0,则 ii 为首领;否则 PiP_i 为 ii 的直属上线。保证这些关系构成一棵树。

第三行一个整数 QQ(1≤Q≤2×1051\le Q\le2\times10^5),表示任务天数。

随后 QQ 行按天给出任务:

  • 1 X Y C:从 XX 向 YY 传递,风险控制值为 CC,其中 1≤X,Y≤n1\le X,Y\le n、0≤C≤n0\le C\le n。
  • 2 T:指派 TT 搜集情报,其中 1≤T≤n1\le T\le n。危险值从开始搜集的日期起计算,不因之后的任务重新计时。

输出格式

每个传递任务输出一行两个整数,中间用一个空格分隔,分别表示参与人数和构成威胁的人数。

样例 #1

样例输入 #1

7
0 1 1 2 2 3 3 
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3

样例输出 #1

5 0
5 2
5 1

样例说明

三次传递均经过 4,2,1,3,74,2,1,3,7。第一次所有人的危险值都是 00;第二次 11、44、77 的危险值分别为 33、22、11,阈值为 11,所以只有前两人构成威胁;第三次阈值为 33,只有 11 号情报员构成威胁。