P3605.第1题-连通器
题目内容
牛牛最近学习了连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中液面总保持相平。如下图所示，四个底部连通的容器液面都是相平的。
牛牛没有图中那么奇怪的容器，他只有 n 支规格相同的试管，这些试管中有一些底部是相互连通的，为了避免混淆试管之间的连通性，牛牛给第 i 支试管标记为 tabi ——若两支试管标记相同，则它们连通。初始时，每支试管中都没有水，且试管体积视为无穷大。现有三种操作：
根据连通器原理，每个连通组内部的水会平分到各支试管中 ，因此,在同一连通组内，每支试管的水量始终相等。
输入描述
第一行输入两个整数 n,m(1≦n,m≦105) ,新试管数量、操作数量。
第二行输入 n 个整数，tab1,tab2,...,tabn(1≦tabi≦n) 表示每支试管的连通标记。
此后 m 行，每行先输入一个整数 o(1≦o≦3) 。表示操作类型，对应三种操作，随后在同一行：
-
若 o=1 ， 输入两个整数 a,b(1≦a≦n;1≦b≦104) ,表示注水操作；
-
若 o=2 ，输入两个整数 a,b(1≦a≦n;1≦b≦104) ，表示抽水操作；保证此时该连通组至少有 b 毫升水可抽；
-
若 o=3 ，输入一个整数 a(1≦a≦n)，表示查询操作。
除此之外，保证至少存在一次查询操作。
输出描述
对于每个查询操作，新起一行输出一个实数，表示第 a 支试管中水的体积。
由于实数的计算存在误差，当误差的量级不超过 10−5 时，您的答案都将被接受。具体来说，设您的答案为 a ，标准答案为 b ，当且仅当 max(1,∣b∣)∣a−b∣≤10−5 时，您的答案将被接受。
样例1
输入
5 6
1 2 1 2 3
1 1 5
3 1
1 2 7
3 4
2 4 4
3 2
输出
2.500000
3.500000
1.500000
说明
在这个样例中，第 1 支试管和第 3 支试管连通，第 2 支试管和第 4 支试管连通。操作如下:
-
注水:向第 1 支试管中注入 5 毫升水，此时第 1,3 支试管中各有 2.5 毫升水;
-
注水:向第 2 支试管中注入 7 毫升水，此时第 2,4 支试管中各有 3.5 毫升水；
-
抽水 : 从第 4 支试管中抽出 4 升水，此时第 2,4 支试管中各有 1.5 毫升水。需要注意的是，虽然直观地看第 4 支试管中此时只有 3.5 毫升水，但是第 4 支试管所在的整个连通器中有 7 毫升水，因此牛牛是可以抽取 4 升水的。
样例2
输入
6 8
1 2 2 2 3 1
1 3 10
3 2
2 3 2
3 3
1 1 9
1 5 10
3 5
3 6
输出
3.333333
2.6666667
10.000000
4.500000
