IOIISL08 - Islands

## 题目描述 你准备游览一个公园，该公园由 $N$ 个岛屿组成，当地管理部门从每个岛屿 $i$ 出发向另外一个岛屿建了一座长度为 $L_i$ 的桥。桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。但相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制： - 你可以任意选择一个岛开始游览。 - 每一个岛都只能游览一次。 - 无论任何时间，你都可以从当前所在的岛 $S$ 去另一个从未到过的岛 $D$。从 $S$ 到 $D$ 有如下方法： - 步行：**仅当两个岛之间有桥时才可以步行**。如果你选择步行，桥的长度会累加到你步行的总距离中。 - 渡船：你可以选择这种方法，仅当没有**任何桥和以前使用过的渡船的组合**可以由 $S$ 走到 $D$。 注意，你不必游览所有的岛，也可能无法走完所有的桥。 请你编写一个程序，给定 $N$ 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。 ## 输入格式 第一行包含一个整数 $N$，表示公园内岛屿的数目。 随后的 $N$ 行每一行用来表示一个岛。第 $i$ 行由两个以空格分隔的整数，表示由岛 $i$ 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 $L_i$。 ## 输出格式 一个整数，表示可能的最大步行距离。 ## 样例 ### 样例输入 ``` 7 3 8 7 2 4 2 1 4 1 9 3 4 2 3 ``` ### 样例输出 ``` 24 ``` ## 提示 **样例解释**：  一共有 $7$ 座桥，如图所示。注意连接岛 $2$ 与岛 $7$ 之间有两座不同的桥。 其中一个可以取得最大的步行距离的方法如下： - 由岛 $5$ 开始。 - 步行长度为 $9$ 的桥到岛 $1$。 - 步行长度为 $8$ 的桥到岛 $3$。 - 步行长度为 $4$ 的桥到岛 $6$。 - 搭渡船由岛 $6$ 到岛 $7$。 - 步行长度为 $3$ 的桥到岛 $2$。 最后，你在岛 $2$，你的总步行距离为 $9+8+4+3=24$。 只有岛 $4$ 没有去。因为上述游览结束时，无法游览此岛。原因如下： - 你不可以步行去游览，因为没有桥连接岛 $2$ (你现在的岛) 与岛 $4$。 - 你不可以搭渡船去游览，因为你可由当前所在的岛 $2$ 到达岛 $4$。一个方法是：走 $(2-7)$ 桥，再搭你曾搭过的渡船由岛 $7$ 去岛 $6$，然后走 $(6-3)$ 桥，最后走 $(3-4)$ 桥。 **数据范围**： 对于 $100\%$ 的数据，$2\le N\le 10^6,1\le L_i\le 10^8$。

You are visiting a park which has **N** islands. From each island i, exactly one bridge was constructed. The length of that bridge is denoted by **Li**. The total number of bridges in the island is **N**. Each bridge can be traversed in both directions. Also, for each pair of island, there is a unique ferry that travels back and forth between them. Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross subject to the constraints below : - You can start a visit on an island of your choice. - You may not visit any island more than once. - At any time you may move from your current island S to any island D which you have not visited before. You can go from S to D either by walking, in which case the length of the bridge you take will be added to the total length or by ferry if the islands are not connected by any bridge (when checking for connectivity you should include those islands which have been previously visited by you). Note that you do not have to visit all the islands, and it may be impossible to cross al the bridges. Given N bridges along with their lengths, your task is to find out the maximum distance you can walk by following the rules above. **Constraints :** 2 <= N <= 100000 1 <= Li <= 1000000 **Input** ------------ The first line of the input contains N, the number of islands. Islands are numbered 1 to N inclusive. Then follow N lines. The ith of these lines contains two integers Ii and Li, which are the island the ith island connects to and the length of the bridge respectively. You may assume that each bridge has two different islands as its endpoints. **Output** ------------- You must write a single line which is the maximum possible distance that you can walk. **Example** -------------- **Input :** 7 3 8 7 2 4 2 1 4 1 9 3 4 2 3 **Output :** 24 **Explanation of the example :** Start at 5. Walk to 1. Walk to 3. Walk to 6. Ferry to 7. Walk to 2. Hence total distance you walked is 9 + 8 + 4 + 3 = 24. **Note :** The final answer fits within 64 bit integer.