博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[codeforces 519E]E. A and B and Lecture Rooms(树上倍增)
阅读量:4622 次
发布时间:2019-06-09

本文共 408 字,大约阅读时间需要 1 分钟。

题目:http://codeforces.com/problemset/problem/519/E

题意:给你一个n个点的树,有m个询问(x,y),对于每个询问回答树上有多少个点和x,y点的距离相等

分析:对于x,y,容易知道距离相等的点是链x->y上的中点除去x、y所在子树的其他所有子树的和

于是分类:

链x->y的长度是奇数:则一定没有距离相等的点,输出0

链x->y的长度是偶数:

  链上的中点Mid恰好是x,y的lca,则输出n-size[lca(x,y)的某个儿子(这个儿子是x的父亲)]-size[lca(x,y)的某个儿子(这个儿子是y的父亲)]

  链上的中点mid不是lca,那么必然在x->lca这条链上,那么输出size[mid]-size[x]

注意对于某个询问x=y的情况,此时输出n

转载于:https://www.cnblogs.com/wmrv587/p/4364061.html

你可能感兴趣的文章
Spring3升级到Spring4时, 运行时出现找不到MappingJacksonHttpMessageConverter的情况
查看>>
详解缓冲区溢出攻击以及防范方法
查看>>
分布式事务解决方案(一) 2阶段提交 & 3阶段提交 & TCC
查看>>
android之网格布局和线性布局实现注册页面
查看>>
BZOJ 1014: [JSOI2008]火星人prefix( splay + hash )
查看>>
安装ejabberd2并配置MySQL为其数据库
查看>>
angular repeat
查看>>
android 图片圆角化控件
查看>>
java第三次作业
查看>>
HP Jack介绍
查看>>
敏捷软件开发(3)---COMMAND 模式 & Active Object 模式
查看>>
poj 1062 昂贵的聘礼 解题报告
查看>>
get the page name from url
查看>>
visual studio中csproj文件中的project guid改为小写 ( notepad++ 正则)
查看>>
TeeChart显示三维的图形,使用Surface
查看>>
如何使用 Idea 远程调试 Java 代码
查看>>
加密,解密
查看>>
在C#代码中应用Log4Net(一)简单使用Log4Net
查看>>
[转]如何写软件项目技术标
查看>>
每日站立会议个人博客五
查看>>