#PQJ1639x7591. QOJ 1639_7591

    ID: 2671 传统题 5000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2014树上算法倍增

QOJ 1639_7591

IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 插线板 【问题描述】 Allison 有非常多的电子设备,比如iMac, iPod, iPhone 和iPad。所以她准备 购买插线板来给电子设备充电。在做了大量的网络调研后,Allison 发现了一款 美丽精巧的天翼牌排插(如左下图所示)。在见到这个插线板的第一眼,Allison 就被它的精美造型所吸引,于是她一次性购买了𝑛个这种型号的插线板。 可是问题也随之而来,Allison 的家中只有一个插座,她需要通过插线板的 连接将电一层一层地导出(如右上图所示)。 插线板的连接方式是树形结构的:每个插线板的插头插在另一个插线板的插 孔中(除了根节点),插线板的连接不允许构成环。 每个插线板有火线,零线,地线三根导线,随着插线板数量的增加、导线的 磨损,电路中的导线与导线之间接触产生的电阻已经到了不能被忽视的地步。 如何来描述插线板的树结构以及导线之间的电阻关系呢?Allison 思考出了 一个数学模型:用𝑎𝑖代表第𝑖个插线板的编号,𝑓𝑖代表第𝑖个插线板的插头所插的 插线板(即𝑎𝑖在树中的父亲),1代表火线,2代表零线,3代表地线,则整个电路 的电阻可以用𝑅(𝑎𝑖, 𝑓𝑖, 𝑥, 𝑦)(𝑥, 𝑦∈{1,2,3})来描述,它代表𝑎𝑖的𝑥线与𝑓𝑖的𝑦线之间 的电阻值(在这个数学模型中,Allison 认为火线和零线也是可能连接并且产生 电阻的)下面是一个例子: 第4 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 由于时间的推移,导线与导线之间的电阻还可能发生变化。现在,Allison 想知道在插线板树形电路中,当前时刻𝑎𝑖插线板的𝑥线和𝑎𝑗插线板的𝑦线之间的电 阻是多少。规定插线板的树根节点不再插向其它插线板,且编号为1。 【输入格式】 输入文件circuit.in 的第一行包含一个正整数𝑛,表示插线板的个数。 接下来4(𝑛−1)行,每4行为一个块。 第𝑖个块的第一行为一个整数𝑓𝑖,表示编号为𝑖+ 1的插线板的父亲为𝑓𝑖插线板。 接下来一个3 × 3的矩阵𝑔𝑥𝑦,第𝑥行第𝑦列表示编号为𝑖+ 1的插线板的𝑥线和 𝑓𝑖的𝑦线之间的电阻的倒数。 接下来一个整数𝑞,表示𝑞个操作数。 接下来𝑞行,每行包含若干个整数。 第一个整数为𝑘,若𝑘= 1,则接下来包含四个整数𝑎𝑖, 𝑥𝑖, 𝑥𝑗, 𝑔,表示将𝑎𝑖插 线板的𝑥𝑖线与𝑎𝑖插线板的父亲𝑓𝑖的𝑥𝑗线之间的电阻值改为𝑔的倒数。保证2 ≤𝑎𝑖≤ 𝑛。 若𝑘= 2,则接下来包含四个整数𝑎𝑖, 𝑥𝑖, 𝑎𝑗, 𝑥𝑗,表示询问𝑎𝑖插线板的𝑥𝑖线与𝑎𝑗插 线板的𝑥𝑗线之间的电阻值的大小。保证𝑎𝑖≠𝑎𝑗。 【输出格式】 输出文件circuit.out。 对于每一个询问,输出一行实数,表示两条线之间的电阻。 选手输出−标准输出 | < 10−3,则被认为该电阻值正确,若所有电阻值皆正确, 若| 标准输出 则获得该测试点的得分。 【样例输入1】 3 1 6 7 1 4 1 8 8 3 3 2 7 5 8 10 5 7 10 5 5 10 1 3 1 2 2 第5 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 插线板 1 2 2 3 5 2 3 2 2 2 1 2 3 2 5 1 3 1 2 3 2 1 2 2 3 1 3 2 1 2 2 2 1 1 1 1 2 1 2 5 2 3 1 1 2 【样例输出1】 0.083836 0.095256 0.078828 0.146900 【样例输入输出2】 见选手目录下的circuit/circuit.in 与circuit/circuit.ans。 【数据规模和约定】 对于所有的测试数据,输入保证是一棵树。0 < 输入中电阻的倒数≤10。 测试点编号 特点 1~6 𝑛≤100, 𝑞≤1000,保证输入中只有查询没有修改 7~10 𝑛≤1000, 𝑞≤1000,保证数据是一条链 11~16 𝑛≤10000, 𝑞≤10000,保证树的高度不超过30 17~20 𝑛≤10000, 𝑞≤10000 第6 页 共9 页