P3363 Cool loves jiaoyi

    • 22通过
    • 247提交
  • 题目提供者 Scarlet
  • 评测方式 云端评测
  • 标签 zkw线段树 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    Cool 交易得十分熟练。现在 Cool 即将参加一场 NOIP 普及组模拟赛。Cool什么都不会,他将通过交易来获得每一题的题解/标程。

    题目描述

    Cool 的交易对象构成了一个树形结构。

    对于每一场轰轰烈烈的交易,都会有一个交易起点和交易终点。在树上从交易起点到交易终点的路径称作交易链,交易链上的所有交易对象都将加入这场交易,交易的代价即为交易对象数。

    现在 Cool 面临着 m 场交易,现在 Cool 要钦点 k 场交易,使得存在某个神秘交易对象参与了所有 k 场交易,并且最小化这 k 场交易中代价之差的最大值。

    输入输出格式

    输入格式:

    输入包含若干行。

    第一行三个整数,n, m, k,代表交易对象数、交易场数和 Cool 钦定的 k。接下来的n − 1行,每行两个整数u, v,代表交易对象u, v在交易树上相连。

    接下来的m行,每行两个整数s, t,表示每场交易的交易起点和交易终点(起点终点可以重合)。

    输出格式:

    输出包含一个整数,Cool 钦点的最小的最大代价之差,若不存在这样的 k 场交易,输出-1。

    输入输出样例

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

    说明

    选择第1,2,3三场交易,则交易对象3,4,5被同时交易了3次,且三场交易的代

    价分别为3,4,4,他们交易代价之差最大为4 − 3。此时最优。

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