#P4565. [CTSC2018] 暴力写挂

    ID: 3496 远端评测题 4000ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>2018线段树WC/CTSC/集训队O2优化分治最近公共祖先LCA

[CTSC2018] 暴力写挂

题目描述

temporaryDO 是一个很菜的 OIer。在 4 月,他在省队选拔赛的考场上见到了《林克卡特树》一题,其中 k=0k = 0 的部分分是求树 TT 上的最长链。可怜的 temporaryDO 并不会做这道题,他在考场上抓猫耳挠猫腮都想不出一点思路。

这时,善良的板板出现在了空中,他的身上发出璀璨却柔和的光芒,荡漾在考场上。“题目并不难。” 板板说。那充满磁性的声音,让 temporaryDO 全身充满了力量。

他决定:写一个枚举点对求 LCA 算距离的 k=0k = 0O(n2logn)O(n^2 \log n) 的部分分程序!于是, temporaryDO 选择以 11 为根,建立了求 LCA 的树链剖分结构,然后写了二重 for 循环枚举点对。

然而,菜菜的 temporaryDO 不小心开小了数组,于是数组越界到了一片神秘的内存区域。但恰好的是,那片内存区域存储的区域恰好是另一棵树 TT' 。这样一来,程序并没有 RE ,但他求 xxyy 的距离的时候,计算的是

$$\mathrm{depth}(x) + \mathrm{depth}(y) - ({\mathrm{depth}(\mathrm{LCA}(x,y))}+{\mathrm{depth'}(\mathrm{LCA'}(x,y))}) $$

最后程序会输出每一对点对 i,ji, jiji \le j) 的如上定义的“距离” 的最大值。 temporaryDO 的程序在评测时光荣地爆零了。但他并不服气,他决定花好几天把自己的程序跑出来。请你根据 TTTT' 帮帮可怜的 temporaryDO 求出他程序的输出。

输入格式

第一行包含一个整数 nn ,表示树上的节点个数。

22 到第 nn 行,每行三个整数 x,y,vx , y , v ,表示 TT 中存在一条从 xxyy 的边,其长度为 vv

n+1n + 1 到第 2n12n-1 行 ,每行三个整数 x,y,vx , y , v ,表示 TT' 中存在一条从 xxyy 的边,其长度为 vv

输出格式

输出一行一个整数,表示 temporaryDO 的程序的输出。

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

提示

样例解释 1

点对 (3,4)(3, 4) 的距离计算为 3+0(0+(2))=53 + 0 - (0 + (-2)) = 5

数据范围

对于所有数据, 1n3666661\le n \le 366666v2017011328|v| \le 2017011328 。 详细数据范围见下表,表格中的“无” 表示无特殊限制。

测试点编号 nn \le vv TT 是一条链 TT' 是一条链
11 3636 =1=1
22 366366
33 13881388 >0>0
44 19991999
55 26662666
66 56665666
77 86668666
88 1111111111
99 1234512345
1010 366666366666 >0>0
1111
121312\sim 13 >0>0
1414
151615\sim 16 >0>0
1717
182018\sim 20

depth(p)\mathrm{depth}(p)depth(p)\mathrm{depth'}(p) 分别表示树 TTTT' 中点 11 到点 pp 的距离,这里规定,距离指的是经过的边的边权总和,其中 depth(1)=0\mathrm{depth}(1) = 0

LCA(x,y)\mathrm{LCA}(x, y)LCA(x,y)\mathrm{LCA'}(x, y) 分别表示树 TTTT' 中点 xx 与点 yy 的最近公共祖先,即在从 xxyy 的最短路径上的距离根经过边数最少的点。