当前位置: 首页 > news >正文

【CodeForces 208E】Blood Cousins

题意:给你一个森林,m个询问:v,p

求有多少个点(除v外) 与 v的第p个祖先相同

这个题首先要解决找某个点的第p个祖先的问题,可以采用倍增法

记录一个二维数组p[u][i]表示u的第2^i个祖先,那么通过这个数组我们就可以知道u的上面任意深度(相对于u)祖先是谁(巧妙的利用二进制)

具体求法和用法见下,还可以找LCA的

const int POW = 18;  
void dfs(int u,int fa){  
    d[u]=d[fa]+1;  
    p[u][0]=fa;  
    for(int i=1;i<POW;i++) p[u][i]=p[p[u][i-1]][i-1];  
    int sz=edge[u].si

相关文章:

  • 【BZOJ 2243】染色 【树链剖分】
  • 【POJ 2484】A Funny Game 【简单博弈】
  • 【POJ 2348】Euclid's Game 【简单博弈】
  • 【BZOJ 2038】小Z的袜子【莫队+分块裸题】
  • python文件操作
  • 【洛谷P1361】小猫爬山
  • 【售货员的难题】
  • c++ 随机数
  • 【算法复杂度分析】主定理
  • 【BZOJ 3289】Mato的文件管理 【莫队+BIT】
  • 【BZOJ 2336】任务调度 【随机化】
  • 【BZOJ 4542】大数 【莫队】
  • 【BZOJ 1003】[ZJOI2006]物流运输 【SPFA+DP】
  • 【BZOJ 1001】狼抓兔子 【Dinic最小割】
  • Dinic模版+SAP模版
  • Angular 响应式表单之下拉框
  • CSS 专业技巧
  • css选择器
  • E-HPC支持多队列管理和自动伸缩
  • ES6核心特性
  • git 常用命令
  • HTTP中的ETag在移动客户端的应用
  • leetcode46 Permutation 排列组合
  • mysql中InnoDB引擎中页的概念
  • SQLServer之创建数据库快照
  • 构造函数(constructor)与原型链(prototype)关系
  • 聚类分析——Kmeans
  • 那些被忽略的 JavaScript 数组方法细节
  • 一个项目push到多个远程Git仓库
  • 因为阿里,他们成了“杭漂”
  • 栈实现走出迷宫(C++)
  • 终端用户监控:真实用户监控还是模拟监控?
  • media数据库操作,可以进行增删改查,实现回收站,隐私照片功能 SharedPreferences存储地址:
  • 阿里云IoT边缘计算助力企业零改造实现远程运维 ...
  • ​Spring Boot 分片上传文件
  • ​软考-高级-系统架构设计师教程(清华第2版)【第9章 软件可靠性基础知识(P320~344)-思维导图】​
  • #includecmath
  • (03)光刻——半导体电路的绘制
  • (BFS)hdoj2377-Bus Pass
  • (C#)一个最简单的链表类
  • **PHP二维数组遍历时同时赋值
  • .h头文件 .lib动态链接库文件 .dll 动态链接库
  • .locked1、locked勒索病毒解密方法|勒索病毒解决|勒索病毒恢复|数据库修复
  • .Mobi域名介绍
  • .NET/C# 避免调试器不小心提前计算本应延迟计算的值
  • .NET多线程执行函数
  • .NET关于 跳过SSL中遇到的问题
  • .Net面试题4
  • /deep/和 >>>以及 ::v-deep 三者的区别
  • @NoArgsConstructor和@AllArgsConstructor,@Builder
  • [ 英语 ] 马斯克抱水槽“入主”推特总部中那句 Let that sink in 到底是什么梗?
  • [BUUCTF 2018]Online Tool(特详解)
  • [C#]使用PaddleInference图片旋转四种角度检测
  • [C++打怪升级]--学习总目录
  • [cocos creator]EditBox,editing-return事件,清空输入框