G. xlb的旅行

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

神仙 xlb 在AK完比赛后决定给自己放个假。于是他来到一个城市,这个城市中有些景点可互相到达,每个景点有一个坐标。

现在 xlb 有这个城市景点的地图,这个城市的地图形成了一棵树,景点编号为 1 ~ n 。且 1 号景点为树的根,其他景点是由根节点向外延伸的,当然连接两个景点的距离是不尽相同的。

由于 xlb 是神仙,所以他只会选择每棵子树中他最感兴趣的景点去玩。

xlb 对每个节点的感兴趣程度为所有连向它的边距离的异或和。

现在他想从他感兴趣的景点中选择几个去玩,他想使这些景点围成图形的面积最大,且图形一定会包含根节点,题目保证有解。

输入格式

第一行一个正整数 n ,表示地图上的城市个数 接下来 n-1 行,每行三个正整数 x、y、w ,表示 x,y 的距离为 w 。 接下来 n 行,每行两个整数 x_i y_i ,其中第 i 行表示第 i+1 个点的坐标 (-1,000,000 \leq x,y \leq 1,000,000)

输出格式

输出必须包括一个整数,表示面积最大时的周长。答案保留两位小数 。

样例

input

4

1 2 68 

1 3 57 

1 4 10 

5 10

4 8

4 12

7 8

output

12.00

数据范围与提示

对于10%的数据, n\leq 10 w\leq 100 -200\leq x_i,y_i \leq 200

对于60%的数据, n\leq 1,000 w\leq 1,000 -50,000\leq x_i,y_i \leq 50,000

对于100%的数据, n\leq 100,000 w\leq10,000 -1,000,000 \leq x_i,y_i \leq 1,000,000