#P4448. [Scoi2015]情报传递
[Scoi2015]情报传递
[SCOI 2015] 情报传递
题目描述
名情报员组成一棵树。除一名首领外,每人有且只有一名直属上线,彼此只能沿这棵树的边联系。公司每天恰好派发一个任务。
- 搜集情报:指派一名情报员开始搜集。所有人的危险值最初都是 。若某人从第 天开始搜集情报,则第 天危险值仍是 ,之后每天增加 ;没有开始搜集的人危险值一直为 。
- 传递情报:从情报员 向情报员 传递,参与者是两人之间唯一简单路径上的所有情报员,包括两端。当天危险值严格大于风险控制值 的参与者构成威胁。传递本身不改变危险值。
对每个传递任务,求参与者总数以及其中构成威胁的人数。
输入格式
第一行一个整数 ()。
第二行 个整数 ()。若 ,则 为首领;否则 为 的直属上线。保证这些关系构成一棵树。
第三行一个整数 (),表示任务天数。
随后 行按天给出任务:
1 X Y C:从 向 传递,风险控制值为 ,其中 、。2 T:指派 搜集情报,其中 。危险值从开始搜集的日期起计算,不因之后的任务重新计时。
输出格式
每个传递任务输出一行两个整数,中间用一个空格分隔,分别表示参与人数和构成威胁的人数。
样例 #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
样例说明
三次传递均经过 。第一次所有人的危险值都是 ;第二次 、、 的危险值分别为 、、,阈值为 ,所以只有前两人构成威胁;第三次阈值为 ,只有 号情报员构成威胁。