题目
其实 Kano 曾经到过由乃山，当然这名字一看山主就是 Yuno 嘛。当年 Kano 看见了由乃山，内心突然涌出了一股杜甫会当凌绝顶，一览众山小的豪气，于是毅然决定登山。
但是 Kano 总是习惯性乱丢垃圾，增重环卫工人的负担，Yuno 并不想让 Kano 登山，于是她果断在山上设置了结界……
Yuno 为了方便登山者，在山上造了 N 个营地，编号从 0 开始。当结界发动时，每当第 i(>0)号营地内有人，那么他将被传送到第 Ai(<i)号营地，如此循环，所以显然最后只会被传送到第 0 号营地。
但 Kano 并不知晓结界的情况。他登山的方法是这样的：首先分身出一个编号为 Gi 的 Kano，然后将其用投石机抛掷到营地 Di。Kano 总共做了 M 次这样的登山操作，但每次抛出去的 Kano 都被传送回了营地 0，所以 Kano 只好放弃了。
但是 Kano 在思考一个问题，到底每个营地被多少只编号不同的 Kano 经过过？
输入格式
第一行两个整数 N,M，表示山的营地数和登山次数。
接下来 N−1 行，每行一个数，第 i 行为 Ai，表示营地 i 将会传向营地 Ai。
接下来 M 行，每行两个数 Di,Gi。
输出格式
共 N 行，每行表示营地 i 有多少不同编号的 Kano 曾经通过。
样例数据
Input
5 400114 13 12 24 2
Output
22112
样例解释
1 号 Kano 曾被抛到 3,4 两个营地，传送轨迹分别是 3−1−0, 4−1−0
2 号 Kano 曾被抛到 2,4 两个营地，传送轨迹分别是 2−0, 4−1−0
所以 0,1,4 号营地被两只 Kano 经过过，2,3 号营地被一只 Kano 经过过。
数据规模与约定
\(5≤N≤100000,10≤M≤100000,max(Gi)≤1000000000\)
时间限制：1s
空间限制：512MB
思路
首先来想一想本题的暴力解法.
很直观的思路是对每一个营地用数组(或\(vector\)/\(set\)/\(queue\)/线段树/平衡树)维护一个集合,存放到达过该点的\(Kano\)的编号.当第\(i\)号营地里的\(Kano\)被传送到第\(A_i\)号营地时,把维护的第\(i\)号营地的集合合并到第\(A_i\)号营地的集合里.最后,每个营地的集合去重后的大小,就是曾经经过了该营地的不同编号的\(Kano\)的数量.
这样就有两个问题:一是合并的顺序;二是怎么合并两个数据结构.
第一个问题很好回答:我们可以倒序从\(n\)到\(1\)遍历序列,每次计算出该营地的答案,同时把该营地的数据合并到\(A_i\)营地.这是因为\(A_i<i\),也就是说,无论哪次合并,都是"从后面的某个营地合并到前面的某个营地".换句话说,一个营地的状态,只与它和它后面的某些营地有关.
第二个问题也很好回答,只需要按照启发式合并的思想,每次都将小的集合合并到大的集合,这样可以获得优秀的\(O(nlog_2^n)\)的时间复杂度.
在代码实现中我使用了\(STL-set\),以省去去重的环节.
代码
#include#include using namespace std;int n,A[100005],m,G,D,Ans[100005],ID[100005];set x[100005];inline void Merge(int u,int v){ if(x[ID[u]].size()