#2116. 暴力写挂
暴力写挂
暴力写挂
题目描述
第一试暴力写挂(wronganswer) IOI 2018 中国国家队选拔赛暨精英赛 暴力写挂(wronganswer) 【题目描述】 temporaryDO 是一个很菜的OIer。在4 月,他在省队选拔赛的考场上见到了《林 克卡特树》一题,其中k = 0 的部分分是求树T 上的最长链。可怜的temporaryDO 并 不会做这道题,他在考场上抓猫耳挠猫腮都想不出一点思路。 这时,善良的板板出现在了空中,他的身上发出璀璨却柔和的光芒,荡漾在考场 上。‘‘题目并不难。’’ 板板说。那充满磁性的声音,让temporaryDO 全身充满了力量。 他决定:写一个枚举点对求LCA 算距离的k = 0 的O(n2 log n) 的部分分程序!于是, temporaryDO 选择以1 为根,建立了求LCA 的树链剖分结构,然后写了二重for 循 环枚举点对。 然而,菜菜的temporaryDO 不小心开小了数组,于是数组越界到了一片神秘的内 存区域。但恰好的是,那片内存区域存储的区域恰好是另一棵树T ′。这样一来,程序 并没有RE,但他求x 和y 的距离的时候,计算的是 depth(x) + depth(y) −(depth(LCA(x, y)) + depth′(LCA′(x, y))) 最后程序会输出每一对点对i, j(i ≤j)的如上定义的‘‘距离’’ 的最大值。 temporaryDO 的程序在评测时光荣地爆零了。但他并不服气,他决定花好几天把 自己的程序跑出来。请你根据T 和T ′ 帮帮可怜的temporaryDO 求出他程序的输出。 【输入格式】 从文件wronganswer.in 中读入数据。 第一行包含一个整数n,表示树上的节点个数; 第2 到第n 行,每行三个整数x、y、v,表示T 中存在一条从x 到y 的边,其长 度为v; 第n + 1 到第2n −1 行,每行三个整数x、y、v,表示T ′ 中存在一条从x 到y 的 边,其长度为v。 【输出格式】 输出到文件wronganswer.out 中。 输出一行一个整数,表示temporaryDO 的程序的输出。 【样例1 输入】 6 1 2 2 第7 页 共11 页 第一试暴力写挂(wronganswer) IOI 2018 中国国家队选拔赛暨精英赛 1 3 0 2 4 1 2 5 -7 3 6 0 1 2 -1 2 3 -1 2 5 3 2 6 -2 3 4 8 【样例1 输出】 5 【样例1 解释】 点对(3, 4) 的距离计算为3 + 0 −(0 + (−2)) = 5。 【样例2】 见选手目录下的wronganswer/wronganswer2.in 与wronganswer/wron- ganswer2.ans。 【子任务】 对于所有数据,n ≤366, 666,|v| ≤2, 017, 011, 328。 详细数据范围见下表,表格中的‘‘无’’ 表示无特殊限制。 第8 页 共11 页 第一试暴力写挂(wronganswer) IOI 2018 中国国家队选拔赛暨精英赛 T ′ 是一条链 测试点编号 T 是一条链 n <= v 1 36 = 1 2 366 3 1388
0 4 1999 否 否 5 2666 6 5666 7 8666 无 8 11111 9 12345 0 10 是 无 11 是 12 0 否 13 无 14 15 366666 0 是 16 17 否 18 无 否 19 20 【提示】 depth(p) 和depth′(p) 分别表示树T 、T ′ 中点1 到点p 的距离,这里规定,距离 指的是经过的.边的边权总和,其中depth(1) = 0 。 LCA(x, y) 和LCA′(x, y) 分别表示树T 、T ′ 中点x 与点y 的最近公共祖先,即在 从x 到y 的最短路径上的距离根.经.过.边.数.最.少的点。 题目并不难。 第9 页 共11 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
1 2 2
1 3 0
2 4 1
2 5 -7
3 6 0
1 2 -1
2 3 -1
2 5 3
2 6 -2
3 4 8
5