祝馀宫

题面：【模板】重链剖分/树链剖分大秦为你打开题目传送门 题目描述如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。 2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。 3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。 4 x 表示求以 $x$ 为根节点的子树内所有节点值之和 输入格式第一行包含 $4$ 个正整数 $N,M,R,P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含 $N$ 个非负整数，分别依次表示各个节点上初始的数值。 接下来 $N-1$ 行每行包含两个整数 $x,y$，表示点 $x$ 和点 $y$ 之间连有一条边（保证无环且连通）。 接下来 $M$ 行每行包含若干个正整数，每行表示一个操作。 输出格式输出包含若干行，分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果（对 $P$ 取模）。 样例 #1样例输入 #11 ...

题面：FJ’s Favorite Permutation B题目描述Farmer John 有一个长为 $N$（$2\le N\le 10^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，FN 会执行以下操作： 令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$， 如果 $p_1^\prime>p_n^\prime$，他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。 否则，他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。 最终，Farmer Nhoj 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$，或者判断 ...

题面：[COTS 2018] 直方图 Histogram题目背景译自 Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,1G}$。 题目描述给定笛卡尔坐标系中的直方图，宽度为 $n$，第 $i$ 格的高度为 $h_i$。也就是说，对于 $\forall 1\le i\le n$，第 $i$ 格所占矩形的顶点坐标分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$。 给定正整数 $p$，求出满足以下条件的矩形的数量： 矩形的四个顶点的坐标均为整数； 矩形有一条边在 $x$ 轴上； 矩形完全位于直方图内部（可以与边界相切）； 矩形的面积至少为 $p$。 输入格式第一行，两个正整数 $n,p$。 第二行，$n$ 个正整数 $h_1,h_2,\ldots,h_n$。 输出格式输出一行一个整数，表示答案。 样例 #1样例输入 #1126 91 4 4 5 2 3 样例输出 #113 样例 #2样例输入 #21210 53 6 1 3 2 1 5 3 4 2 样例输出 #21 ...

题面：[TJOI2011] 树的序题目描述众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲： 空树中加入一个键值 $k$，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$。 在非空树中插入一个键值 $k$，若 $k$ 小于其根的键值，则在其左子树中插入 $k$，否则在其右子树中插入 $k$。 我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为 $n$ 的生成序列，先比较第一个插入键值，再比较第二个，依此类推。 输入格式第一行，一个整数 $n$，表示二叉查找树的结点个数。第二行，有 $n$ 个正整数 $k_1, k_2, \cdots,k_n$，表示生成序列，简单起见，$k_1 \sim k_n$ 为一个 $1$ 到 $n$ 的排列。 输出格式一行，$n$ 个正整数，为能够生成同样二叉查找树的所有生成序列中最小的。 样例 #1样例输入 #11241 3 4 2 样例输出 #111 3 2 4 提示数据范围及约定 对于 $20\%$ 的数据， $1\l ...

题面：Redundant Paths G大秦为你打开题目传送门 题面翻译为了从 $F(1 \le F \le 5000)$ 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。 每对草场之间已经有至少一条路径．给出所有 $R\ (F-1 \le R \le 10000)$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。 题目描述In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the re ...

题面：[POI2008] BLO-Blockade大秦为你打开题目传送门 题面翻译B 城有 $n$ 个城镇（从 $1$ 到 $n$ 标号）和 $m$ 条双向道路。 每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。 把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。 请你对于每个节点 $i$ 求出，把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【输入格式】 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。 【输出格式】 输出共 $n$ 行，每行输出一个整数。 第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。 【数据范围】 $n\le 100000$，$m\le500000$。 题目描述There are exactly $n$ towns in By ...

题面：[ZJOI2004] 嗅探器大秦为你打开题目传送门 题目描述某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。 蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。 但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。 现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？ 输入格式输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。 接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。 服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。 输出格式输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。 样例 #1样例输入 #112345678952 12 51 45 32 35 10 04 2 样例输出 #111 ...