题意：Takuru 是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru 的计划是让 Hinae 帮他去市场上买一个商品，然后再以另一个价格卖掉它。Takuru 会给 Hinae 一定的钱 $p$。($p$ 是一个非负的实数)这个商品的市场价是一个在 $[l, r]$ 内均匀随机的实数。如果 $p \geqslant$ 市场价，那么 Hinae 会买下这个商品，然后私吞剩下的钱。也就是说，Takuru 以 $p$ 的代价买来了这个商品。如果 $p <$ 市场价，那么 Hinae 既不会买下商品，又不会私吞任何钱。也就是说，Takuru 的利润为 $0$。当 Hinae 买下了商品后，Takuru 会生成一个在 $[L, R]$ 内均匀随机的实数 $q$，并把商品以 $q$ 的价格卖掉。那么 Takuru 的利润就是 $q - p$。Takuru 想要获得最多的利润，所以你要帮 Takuru 确定给 Hiane 的钱 $p$，使得 Takuru 的期望利润最大。请求出最大的期望利润。

题意：

由于需要保证字典序最小，只需要每次从当前可以选择的还没有部署干员的节点中选择编号最小的。记当前没有被选择的所有点的 $a[]$ 的最小值为 $t$，可以用一个 $\texttt{multiset}$ 维护，并且 $t$ 不会减小。受到限制而不能选择的点是深度大于 $t$ 的所有点，每次 $t$ 增大时把从不能选择变成可以选择的点(用一个 $\texttt{vector}$ 维护每个深度的点)加入堆(优先队列)中，每次取最小值即可得到答案。

题意：小 $X$ 有一台奇怪的计算机。这台计算机首先会读入一个正整数 $n$($1\le n\le 10^{18}$)，然后生成一个包含 $n$ 个数的序列 $a$。一开始 $a_i(1 \le i \le n)$ 的值均为 $1$。接下来，小 X 会进行 $n-1$ 次操作，每次操作会输入一个指令，这个指令有 $2$ 种情况：

题意：

小明为了变得越来越神，他给自己制定了 $n$ 个任务，编号为 $1,2,···,n$。小明在完成这些任务之前有一个初始兴奋值 $m$，每个任务都有一个难度值 $hard[i]$,且对于任何 $i>j$，有 $hard[i]>hard[j]$，小明完成第 $i$ 个任务，兴奋值至少会减少 $hard[i]$，第 $i$ 任务完成之后，小明会受到鼓舞，兴奋值又会增加 $s[i]$，每个任务只完成一次。小明可以一次完成所有剩余的难度值不超过现有兴奋度的任务，这样只会消耗那个最大的难度值。现在小明想知道完成这 $n$ 个任务之后，他的最大兴奋值为多少。

题意：小明即将出版新书，以记录他辉煌的虐题生涯。有 $n$ 家出版社对这本书表示了兴趣，并愿意给小明支付 $p\in[Minn,Maxx]$ 的报酬来得到这本书的出版权，每家出版社的 $Minn$ 和 $Maxx$ 是不一样的。 现在小明希望你帮他找出一个报酬值 $p$，使得他获得的总报酬最多。(每一个 $Minn\leq p\leq Maxx$ 的出版社都会付给小明 $p$ 的报酬，$1\leq n\leq 100000,1\leq Minn,Maxx\leq 10^9$)

题意：给定一张 $N$ 个点 $M$ 条边的无向连通图，然后执行 $Q$ 次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量。

求桥的数量，先用 $Tarjan$ 算法，求出所有的边双连通分量(即 $e-DCC$)，然后缩点得到一棵树，树上的边的数量就是桥的数量。

对于每一个添加的边 $(x,y)$，如果 $x$ 和 $y$ 属于同一个 $e-DCC$，那么对答案没有任何影响，答案不变；

题意：$Byteotia$ 城有 $n$ 个城镇，$m$ 条双向道路。每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。输出共 $n$ 行，每行输出一个整数。第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。

题意：

Adera 是 Microsoft 应用商店中的一款解谜游戏。异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。这张地图上有 $N$ 个点，有 $N-1$ 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 $M$ 个时刻中，每个时刻会发生以下三种类型的事件之一：

题意：

根据题意，可以把任意 $S_i$ 到 $T_i$ 之间的路径分为两条边，即：

1. 上行边，从 $S_i$ 到 $LCA(S_i,T_i)$。

2. 下行边，从 $LCA(S_i,T_i)$ 到 $T_i$(不包含 $LCA(S_i,T_i)$)。

对于任意一个上行边上的点 $u$，如果要被观察到，都要满足以下条件：

题意：有一个 $N$ 个点的树，进行 $M$ 次操作，每次选择两个点 $x,y$，对从 $x$ 到 $y$ 的路径上所有的节点放置一个 $z$ 类型的标记。询问操作完成后，每个点存放最多的是哪种类型的标记。

这道题也要用到树上差分的思想，但是与上一道[POJ3417] Network不一样，这次是对所有的点标记，而不是边，这就是点差分。