T1 送信卒
题目信息
* 时间限制: 1s
* 空间限制: 256M
* 输入文件: msg.in
* 输出文件: msg.out
题目描述
在 n×mn \times mn×m 的网格图中，大头兵 u 需要将长官的信件从 (sx,sy)(sx, sy)(sx,sy) 送到 (tx,ty)(tx,ty)(tx,ty)。每个格子上可能有障碍物，有障碍物的格子用 1 表示，这些格子无法通行，其余格子用 0 表示，没有障碍物的格子可以自由通行。u 每次可以选择上下左右任意方向走一格，上下移动需要穿越河流，移动一次耗时为 kkk 秒；左右移动是在陆地行进，移动一次耗时 1 秒。
因为某些原因，u 需要保证从 (sx,sy)(sx, sy)(sx,sy) 到 (tx,ty)(tx,ty)(tx,ty) 的最短路恰好耗时 sss 秒，幸运的是，u 可以任意选择过河交通工具，也就是说过河耗时 kkk 秒可以由 u 决定。但是 u 只能选择同种类型的过河交通工具，也就是说在这次送信任务中所有的 kkk 是统一的。
那么合适的 kkk 是多少呢？
输入格式
第一行两个正整数 n,mn, mn,m。
第二行四个正整数 sx,sy,tx,tysx, sy,tx,tysx,sy,tx,ty，分别表示送信任务的起点和终点坐标。
接下来 nnn 行，每行 mmm 个数，描述网格图。
最后一行一个正实数 sss。
输出格式
输出仅一行一个实数 kkk，表示答案，四舍五入保留 3 位小数，评测时开启逐行比较模式以保证精度。
数据保证有解。如有多解，kkk 应当尽可能小，最小值为 0。
样例
输入1
4 4
1 1 4 4
0 0 1 1
1 0 0 0
0 0 1 0
0 0 0 0
5.00
输出1
0.667
数据范围与提示
对于所有数据，满足 1≤n,m≤100,1≤s≤105,1≤sx,tx≤n,1≤sy,ty≤m1 ≤ n, m ≤ 100, 1 ≤ s ≤ 10^5, 1 ≤ sx,tx ≤ n, 1 ≤ sy,ty ≤ m1≤n,m≤100,1≤s≤105,1≤sx,tx≤n,1≤sy,ty≤m。
子任务编号 分值 特殊性质 1 30 n,m≤10n, m ≤ 10n,m≤10 2 10 特殊性质A 3 60 无
特殊性质 A：n,m≤10n, m ≤ 10n,m≤10，且保证从起点到终点只有一条不重复经过同一个点的路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2 BOSS 树
题目信息
* 时间限制: 1s
* 空间限制: 1024M
* 输入文件: boss.in
* 输出文件: boss.out
题目描述
A 是刺客兄弟会某个年代的传奇刺客，为了探寻 A 的传奇故事，A 的后代 a 借助 Animus 进入了 A 的记忆世界。已知 A 在他的时代刺杀了 nnn 位圣殿骑士，但是 a 目前只知道 A 第一天刺杀了圣殿骑士 1，而第 iii 位圣殿骑士的情报必须通过刺杀圣殿骑士 fif_ifi 来取得（保证 fi≤i−1f_i ≤ i - 1fi ≤i−1）。
a 的精力有限，一天最多只能在 Animus 刺杀 mmm 位圣殿骑士，并且若 fj=if_j = ifj =i，无论 mmm 是多少，a 都不可能在同一天刺杀 i,ji,ji,j，因为 a 必须得离开 Animus 和战友们研究完 iii 的情报才能确定 jjj 的位置。例如，圣殿骑士 3 满足 f3=1f_3 = 1f3 =1，a 可以在第一天刺杀圣殿骑士 1，但是必须在当天结束 Animus，同战友们研究完 1 提供的情报后，才能锁定 3 的位置，在之后的任意一天都可以对 3 展开刺杀任务。
当代的圣殿骑士团依然在追杀刺客兄弟会，a 必须尽快探索完 A 的记忆帮助刺客兄弟会力挽狂澜，那么 a 最少需要多少天才能在 Animus 刺杀所有 nnn 位圣殿骑士呢？
输入格式
第一行两个整数 n,m (1≤n≤105,1≤m≤n)n, m\ (1 ≤ n ≤ 10^5, 1 ≤ m ≤ n)n,m (1≤n≤105,1≤m≤n)。
第二行 n−1n-1n−1 个整数，分别表示 f2,f3,…,fnf_2, f_3,…, f_nf2 ,f3 ,…,fn 。
输出格式
第一行一个整数 ansansans，表示 a 至少要花费的天数。
接下来一共 ansansans 行，每行第一个整数 si(si≤m)s_i(s_i ≤ m)si (si ≤m) 表示第 iii 天刺杀的圣殿骑士数量，接下来 sis_isi 个整数表示当天刺杀的圣殿骑士们的编号。
样例
输入1
5 2
1 1 1 2
输出1
3
1 1
2 2 3
2 4 5
数据范围与提示
对于所有数据，1≤n≤105,1≤m≤n,1≤fi<i1 ≤ n ≤ 10^5, 1 ≤ m ≤ n, 1 ≤ f_i < i1≤n≤105,1≤m≤n,1≤fi <i。
子任务编号 分值 其他限制 1 24 n≤10n ≤ 10n≤10 2 26 m=1m = 1m=1 3 12 n≤16n ≤ 16n≤16 4 38 无
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3 共轭树图
题目信息
* 时间限制: 1s
* 空间限制: 512M
* 输入文件: reflection.in
* 输出文件: reflection.out
题目描述
对于以 1 为根的有根树 TTT，保证 TTT 中每个节点的父节点编号一定大于自身的编号。将 TTT 的边编号为 1,…,n−11,…, n-11,…,n−1，可通过如下方式生成 TTT 的共轭树图 GGG：
1. 选择 1,…,n−11,…, n-11,…,n−1 的一个排列 p1,…,pn−1p_1,…, p_{n-1}p1 ,…,pn−1 ；
2. 依次考虑 i=1,…,n−1i = 1,…, n - 1i=1,…,n−1；
3. 删除编号为 pip_ipi 的边，设其端点分别为 a,ba, ba,b，选择当前树中分别与 a,ba, ba,b 连通的编号最大的点 u,vu, vu,v，在 GGG 中连接边 (u,v)(u, v)(u,v)。
对于树 TTT，总共可能生成出多少种不同共轭树图 GGG 呢？答案对 998244353 取模。
输入格式
第一行一个整数 nnn。
接下来 n−1n-1n−1 行，每行两个整数 a,ba, ba,b，表示一条树边。
输出格式
一行一个整数表示答案对 998244353 取模的结果。
样例
输入1
4
1 4
2 3
3 4
输出1
2
样例解释1：令第 iii 条输入的边编号为 iii。当 ppp 为 {1,3,2}\{1, 3, 2\}{1,3,2} 或 {3,1,2}\{3, 1, 2\}{3,1,2} 或 {3,2,1}\{3, 2, 1\}{3,2,1} 时会生成 E(G)={(1,4),(2,3),(3,4)}E(G) = \{(1, 4),(2, 3),(3, 4)\}E(G)={(1,4),(2,3),(3,4)}。另外三种 ppp 会生成 E(G)={(1,4),(2,4),(3,4)}E(G) = \{(1, 4),(2, 4),(3, 4)\}E(G)={(1,4),(2,4),(3,4)}。
输入2
11
1 4
2 6
3 11
4 6
5 6
6 7
7 9
8 9
9 10
10 11
输出2
4605
数据范围与提示
对于 100% 的数据: 1≤n≤3×1031 ≤ n ≤ 3 × 10^31≤n≤3×103。
Subtask 分值 限制 1 24 pts n≤5n ≤ 5n≤5 2 16 pts n≤14n ≤ 14n≤14 3 8 pts n≤103n ≤ 10^3n≤103，所有其他结点与 1 直接相连 4 8 pts n≤103n ≤ 10^3n≤103，树的形态为一条链 5 22 pts n≤50n ≤ 50n≤50 6 22 pts 无特殊限制
