前言

本题最大的特点就是要写几万年没写过的高精！

~~卡常卡一万年也过不了，淦。~~

题目

题目背景

有一天，小SY想变(_{_{ iny{大}}})~~(大家都知道这不可能)~~，一天他在梦里找到了一棵可以让他变大的树，这棵树有 (n) 个节点，每个节点有两个权值 (a_i,b_i)，根节点为 (1) 号节点，小SY最开始值为 (1)，起点为根节点，他需要找到一条从根节点出发到叶子结点的路径，使得他的值变得最( iny{大})。若小SY现在的值为 (x)，每经过一个节点，他的值会变为 (a_ix+b_i)，你从未来得知他在两秒之后就会醒来，并且忘掉了这个最大值是多少，醒来时他会询问你，如果你不能回答这个问题，那么他就会非常生气，后果不堪设想。由于小SY认为取模后他会变小，所以他不允许你取模，请老老实实回答。

题目描述

通俗点来讲是这样的：

有一棵 (n) 个点的树，每个节点有 (a_i,b_i) 两个权值，每经过一个节点你的得分就会先乘上 (a_i) 再加上 (b_i)，你的初始分数为 (1)，你需要找到一条最大化你得分的从根节点到一个叶子节点的路径，然后输出最大得分。根节点为 (1) 号节点。无取模。

数据范围

对于所有数据，保证 (a,b) 在 ([1,9]) 内均匀随机，(1≤n≤5×10^5)。

( ext{subtask}1(20pts):n≤50)

( ext{subtask}2(20pts):n≤5000)

( ext{subtask}3(20pts):)保证 (∀0<i<n)，(i) 到 (i+1) 都有一条边。

( ext{subtask}4(40pts):) 无特殊限制。

时空限制

时间限制：(2s)

空间限制：(512M)

讲解

part1 (nle 5000)

对于前 ( t 40pts)，只要写一个像样的压位高精(普通高精没试过，不推荐)，而且只需要满足高精乘低精、加低精，高精之间比较大小即可，写得不算特别特别特别丑应该都能过。高精竟然出乎意料地好写，直接过掉。

part2 链

由于有且仅有一条路径，我们可以考虑分治。

对于先后两个操作 ((a_i,b_i)) 和 ((a_j,b_j)) ，显然可以合并成一个操作：((a_ia_j,a_jb_i+b_j))，分治( t FFT)优化高精乘即可。

时间复杂度 (O(nlog^2n))。

part3 正解

从 ( t part2) 已经可以得知计算的方法，只需要找到一条最大的路径即可。利用随机性质，我们让比较的精度在 ( t double) 范围内，具体怎么做呢？

乱搞。

根据数据随机，我们可以采用 科学计数法！我们可以写成 (o*10^p,(oin[1,10),pin Z)) 的形式，(o) 的精度不会爆的吧。

搞定！

代码

作为聪明的读者，你一定可以自己写出来的！がんばって！파이팅！加油！come on!