回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共3篇）

P3806 【模板】点分治1

模板题 P3806 【模板】点分治1 题目描述给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。详讲关于点分治具体内容可以看这个这里主要是详细讲讲代码：getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可 void getrt(int u...

** 点分治

2021-02-23

0 560

点分治（树分治）

@[toc] 介绍：将原问题分解成若干相同形式，相互独立的子问题，各个击破一般用来解决有关树上路径的统计和询问题目： P4178 Tree给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。做法：暴力做法；(O(n^2^))点分治做法：选择一个点作为分治中心，令...

点分治

2021-02-23

0 569

P4178 Tree

P4178 Tree 题意：给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。题解：点分治的模板题是求等于K的路径条数本题是求小于等于K的路径条数，我们只需要改变统计答案即可原本统计答案是对一个路劲长度len，判断K-len在之前的子树中出现多少次，用f数组来记...

**** 点分治

2021-02-23

0 681