首页 > A and B and Lecture Rooms
开通博客写题解
头像 hnust_yangyanjun
发表于 2020-11-29 20:07:04
题意：有一颗n个节点的树，有m个询问，每个询问给出x和y两个节点，让你求树上节点到这两个节点距离相等的数目。 思路：①：如果x和y深度相同，则他们的最近公共祖先lca（x,y)的非这二个节点方向的节点以外的节点到x和y的距离相等.②：如果x和深度不同，则他们的路径为奇数时无解，为偶数时中点在深度大的 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 lifehappy
发表于 2020-11-26 20:54:05
A and B and Lecture Rooms 题意要求我们找有多少个点满足，输出点的数量即可。 首先特判无解的情况就是为奇数时，接下来我们讨论有解的情况，大致分为两类。 首先我们一定可以在的路径上找到一个点满足要求。 这个点不在上：如图我们要找的是(5, 6)的满足要求的点有多少个，显然3是 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-11-27 15:40:11
这题的思维难度并不很大 但是细节有一点点需要注意 首先两点间的距离如果是奇数必定无解 如果是偶数,那么可以找到中间的那个点,必定满足条件 而且从延伸出去的各种分支,只要不是包含的分枝都是满足条件的 因为两点都是从拐过去的 这个规律在任意时刻都是适用的 但是当deep[l]==deep[r]注意一下计 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 林思艺
发表于 2020-11-25 20:50:28
题意 题目的意思就是每次询问点x，y，要你求其中离它们距离一样的点有多少个。 分析 我们可以先找到这两个点的 ，然后路径的中点肯定是一个解（没有就无解咯）。然后从这个点不经过 这条路径任意一点能到达的点，就是其他解。求法的话，比较两个询问节点的深度 深度相同： 深度不同： 代码 #inclu 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kur1su
发表于 2020-12-09 11:41:46
Description 给出一棵树， 个询问，每次询问给出 ，需要得到有多少个点距离 相等。 Solution 分类讨论 时，每个点都可以，输出 为奇数时， 显然不存在点满足条件输出 剩余情况我们考虑结合 的特点 如果距离 相等的点在 上，如下图所示从他们的 开始的其他点都满足条件 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 MYCui_
发表于 2021-02-02 19:40:51
CF519E 【A and B and Lecture Rooms】 前言: 你可能需要用到的前置知识点: 倍增求 (或者说是树上倍增？) 正文 题目大意: 给定一棵树，以及 个询问，每次询问的形式是给定两个点 ，求有多少个点 满足 题目不难 ，但是要分类讨论清楚也不是那么容易。 无根树，我 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2020-12-01 13:18:36
做法：lca 题意： 已知两点，求到这两点距离相同的点的个数 思路： 如果存在到这两点距离相同的点，那么这两点的距离一定是偶数 如果这两点的深度相同，那么他们向上走到他们最近的公共祖先的子节点，然后n减去以这两个点为根节点的子树大小 否则求减去这两个点的中点一下的部分 代码 // Prob 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”