首页 > 其他分享 >【学习笔记】圆方树

【学习笔记】圆方树

时间:2022-09-18 11:37:43浏览次数:116  
标签:方点 圆点 笔记 学习 圆方树 例题 仙人掌 赋值

同学们都会树的定义了吧,那么接下来我们来学习圆方树吧

圆方树

基础理论

圆方树,适用于仙人掌上问题,可将仙人掌转化为普通树。
将仙人掌上的点双连通分量合成一个方点(tarjan),剩余点作为圆点,其上做普通树处理即可。

(说起来很简单,来看一道例题吧!)

例题

P4320 道路相遇

简化题面:给出一张无向图, $ q(1<=q<=5e5) $ 次询问,每次询问给出两点,求两点路径上有多少个必须经过的点。

直接上圆方树,将圆点赋值为1,方点赋值为0,求路径和即可。

(据说树剖比倍增快)

(这道题用LCT的是魔鬼吧)

标签:方点,圆点,笔记,学习,圆方树,例题,仙人掌,赋值
From: https://www.cnblogs.com/T-water/p/16704481.html

相关文章

  • 信安系统学习笔记三
    第十章、sh编程一.知识点归纳(一)sh脚本-sh脚本是一个包含sh语句的文本文件,命令解释程序sh要执行该语句。shebang(#!)的一些具体用法:如果脚本文件中没有#!这一行,那......
  • 5.Maven学习
    尚硅谷-Maven教程笔记1.maven:(项目管理工具)构建管理工具,依赖管理工具第一章Maven概述第一节为什么要学习Maven?1.Maven作为依赖管理工具(1)jar包规模过大(2) jar包的来源......
  • 20201320第三周学习笔记
    sh编程sh脚本sh脚本是一个包含sh语句的文本文件,命令行解释程序sh要执行该语句。创建mysh:1#!/bin/bash2#commentline3echohello 使用chmod-xm......
  • buf 工具对于buf使用的学习
    buf就是基于buf开发的,有不少实践可以参考学习bufbuf项目结构如下图  使用说明buf.yaml主要定义包  包命名  代码生成基本模式  包含......
  • Markdown学习
    Markdown学习第一天(效果加格式)注:所有格式用英文字体hello,world!'****'hello,world!'**'hello,world!‘**’hello,world‘~~~~’引用'>'“接空格”选择坚持,弥......
  • C语言学习
    1.I/O:input&output是一切实现的基础stdio标准IOsysio系统调用IO(文件IO)如果一个系统环境下,2中io都可以使用,当然优先使用标准io2.标准库函数都在man手......
  • C++学习笔记-day16
    1、模板......
  • 深度学习:计算性能
    1、命令式和符号式混合编程命令式编程,它使用编程语句改变程序状态:defadd(a,b):returna+bdeffancy_func(a,b,c,d):e=add(a,b)f=add(c,d)......
  • 道长的算法笔记:动态规划经典模型
    (一)背包模型Waiting...(二)数字三角形模型Waiting...(三)线性规划模型Waiting...(四)区间规划模型Waiting...(五)状态压缩动规模型Waiting.........
  • ML第24周学习小结
    本周收获总结一下本周学习内容:1、《深度学习》第七章:优化算法7.1优化与深度学习~7.8Adam算法......