P3899 [湖南集训]谈笑风生

    • 564通过
    • 1.6K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 主席树 深度优先搜索,DFS 线段树 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    设 T 为一棵有根树,我们做如下的定义:

    • 设 a 和 b 为 T 中的两个不同节点。如果 a 是 b 的祖先,那么称“a 比 b 不知道高明到哪里去了”。

    • 设 a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数 x,那么称“a 与 b 谈笑风生”。

    给定一棵 n 个节点的有根树 T,节点的编号为 1 ∼ n,根节点为 1 号节点。你需要回答 q 个询问,询问给定两个整数 p 和 k,问有多少个有序三元组 (a; b; c) 满足:

    1. a、 b 和 c 为 T 中三个不同的点,且 a 为 p 号节点;

    2. a 和 b 都比 c 不知道高明到哪里去了;

    3. a 和 b 谈笑风生。这里谈笑风生中的常数为给定的 k。

    输入输出格式

    输入格式:

    输入文件的第一行含有两个正整数 n 和 q,分别代表有根树的点数与询问的个数。

    接下来 n − 1 行,每行描述一条树上的边。每行含有两个整数 u 和 v,代表在节点 u 和 v 之间有一条边。

    接下来 q 行,每行描述一个操作。第 i 行含有两个整数,分别表示第 i 个询问的 p 和 k。

    输出格式:

    输出 q 行,每行对应一个询问,代表询问的答案。

    输入输出样例

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

    说明

    样例中的树如下图所示:

    对于第一个和第三个询问,合法的三元组有 (2,1,4)、 (2,1,5) 和 (2,4,5)。

    对于第二个询问,合法的三元组只有 (4,2,5)。

    所有测试点的数据规模如下:

    对于全部测试数据的所有询问, 1 ≤ p ≤ n, 1 ≤ k ≤ n.

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