CF979C Kuro and Walking Route(简单的dfs/树形dp)
2024-10-06 10:54:00
题意:给出一个$n$个点,$n-1$条边的无向连通图,给出两个点$x,y$,经过$x$后的路径上就不能经过$y$,问可以走的路径$(u,v)$有多少条,($(u,v)$和$(v,u)$考虑为两条不同的路径)。
题目分析:显然这是棵树。。所以从$x$到$y$只有一条简单路径。而且以$x$到$y$的路径上的点为根的话,我们发现不能走的那些点都在$x$,$y$的子树里面。这样的话,统计出$x$子树里的点有$a$个,$y$子树里的点有$b$个,那么整棵树中可以走的路径一共就有$n*(n-1)-a*b$条。
怎么维护:dfs就好啦。
代码不粘了(懒得写了)。
最新文章
- SQL SERVER与SSIS 数据类型对应关系
- 解决:Redis:java.util.NoSuchElementException: Unable to validate object at
- Index/Common目录下文件
- 今天踩过的坑——structs和spring
- UVALive 6073 Math Magic
- 24c16读写驱动程序
- sed用法小结
- spring学习——注入静态对象属性
- AVPlayer缓存实现
- Python课程学习总结
- Vue项目在开发环境跨域和生成环境部署跨域问题解决
- Java JSONArray for循环 remove成员的一个好算法
- 软硬连接ln
- C# 绘图时使用抗锯齿会多出一个像素
- Oracle错误——SP2-0734: 未知的命令开头 ";imp C##sin..."; - 忽略了剩余的行。
- CentOS7.3环境下源码安装httpd
- 微软MVP社区秋日巡讲 —— 北京Windows Phone应用开发训练营
- [翻译] DBCamera 轻量级定制摄像头
- 自动化运维工具saltstack04 -- 之jinja模板
- Matlab图像匹配问题
热门文章
- 【0806 | Day 9】三张图带你了解数据类型分类和Python深浅拷贝
- hadoop开启Service Level Authorization 服务级认证-SIMPLE认证-过程中遇到的坑
- 洛谷 P3203 [HNOI2010]弹飞绵羊
- sql server 日期近一年,同比
- Unity经典案例之:Fire Balls 多个圆环以及圆环的变速变向
- Mac 打造开发工作环境
- 纯数据结构Java实现(5/11)(Set&;Map)
- SpringBoot与Shiro整合权限管理实战
- .net必问的面试题系列之面向对象
- Vim高手,从来不用鼠标