TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2557
  • 题目
  • P2557Debug-2
    限制 : 时间限制 : 10000 MS   空间限制 : 123456 KB
    问题描述

    经过一整夜的激战,RC的部队终于攻下了虫族的首都bugzilla。现在RC决定亲自带领一突击队在虫族庞大的地道中寻找他的宿命之敌——bug。
    Bugzilla有N个基地组成。这N个基地被N-1段双向地道连接在一起,每段地道都连接两个基地,并且保证任意两个基地之间都可以通过地道互相到达。Bug就藏在其中的某段地道中。
    开始时RC可以乘坐运输机降落在任何一个基地,每次到达一个基地时,RC都可选择呼叫运输机将他和他的部队运输到任一个基地,或者进入与这个基地相邻的一段地道进行搜索。为了防止bug跑进已经搜索过的地道,他在离开一个基地进入地道或登上运输机是一定会将这个基地炸毁,基地一旦被炸毁就不再和它相邻的地道连接。但这样一来,如果进入的地道另一端的基地已经在之前被炸毁,RC和它的部下就被永远困在地道中。RC是不会进入这段地道的。
    这也带来了一个问题,就是RC也许不能搜索所有的地道了。现在RC想知道的是他最多能搜索多地道。作为有幸被留在运输机上看风景而不必冒着成为虫食的危险钻入地下的人,你必须完成这个任务。

    输入格式

    第一行为一个整数N(2<=N<=200000),表示基地的个数,基地被编号为1~N的整数。
    以下N-1行,每行两个整数A,B,D,表示编号为A的基地和编号为B的基地间有一段长度为D地道。

    输出格式

    一个整数,表示RC最长能搜索的地道长度。

    样例输入 1

    样例输入1:
    4
    1 2 1
    1 3 2
    1 4 3 

    样例输入2:
    6
    1 2 3
    1 3 2
    1 4 1
    4 5 2
    4 6 3

    样例输出 1

    样例输入1:
    5

    样例输入2:
    10

    样例输入 2

    24
    2 1 8468
    3 1 6501
    4 1 5725
    5 1 9359
    6 3 4465
    7 6 8146
    8 6 6828
    9 7 492
    10 9 1943
    11 8 5437
    12 10 4605
    13 10 154
    14 11 2383
    15 13 8717
    16 12 9896
    17 14 1727
    18 16 1539
    19 14 9913
    20 17 6300
    21 20 9895
    22 18 3812
    23 20 334
    24 20 4665

    样例输出 2

    97733

    提示

    保证输入数据和答案均不超过231-1且没有负数