P4281 [AHOI2008]紧急集合 / 聚会

    • 148通过
    • 374提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签 最近公共祖先,LCA 树链剖分,树剖 各省省选 2008 安徽
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    欢乐岛上有个非常好玩的游戏,叫做“紧急集合”。在岛上分散有N个等待点,有N-1条道路连接着它们,每一条道路都连接某两个等待点,且通过这些道路可以走遍所有的等待点,通过道路从一个点到另一个点要花费一个游戏币。

    参加游戏的人三人一组,开始的时候,所有人员均任意分散在各个等待点上(每个点同时允许多个人等待),每个人均带有足够多的游戏币(用于支付使用道路的花费)、地图(标明等待点之间道路连接的情况)以及对话机(用于和同组的成员联系)。当集合号吹响后,每组成员之间迅速联系,了解到自己组所有成员所在的等待点后,迅速在N个等待点中确定一个集结点,组内所有成员将在该集合点集合,集合所用花费最少的组将是游戏的赢家。

    小可可和他的朋友邀请你一起参加这个游戏,由你来选择集合点,聪明的你能够完成这个任务,帮助小可可赢得游戏吗?

    输入输出格式

    输入格式:

    第一行两个正整数N和M(N<=500000,M<=500000),之间用一个空格隔开。分别表示等待点的个数(等待点也从1到N进行编号)和获奖所需要完成集合的次数。 随后有N-1行,每行用两个正整数A和B,之间用一个空格隔开,表示编号为A和编号为B的等待点之间有一条路。 接着还有M行,每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

    输出格式:

    一共有M行,每行两个数P,C,用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点,集合总共的花费是C个游戏币。

    输入输出样例

    输入样例#1: 复制
    6 4  
    1 2  
    2 3  
    2 4 
    4 5
    5 6
    4 5 6
    6 3 1
    2 4 4 
    6 6 6
    输出样例#1: 复制
    5 2
    2 5
    4 1
    6 0
    
    
    

    说明

    提示:

    40%的数据中N<=2000,M<=2000
    100%的数据中,N<=500000,M<=500000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。