Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 852人学习

11eyes的排位日记

10篇文章 946人学习

0篇文章 0人学习

全部文章（共4篇）

树的直径

之前写过一篇学军信友队趣味网络邀请赛 B.齐心抗疫，那篇文章中讲述了一种通过两次dfs就足以求得树的直径的方法，今天来学习另一种方法求树的直径——树形DP。定义树的直径：若树上两点u,vu,v间的最短路径最大，那么该路径的长度称为树的直径。（可以存在多条）区别两者的复杂度都是方法1：简洁方便...

树树的直径数据结构

2020-09-17

0 1110

NC51180

题意给定一棵个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。思路换根DP这种题往往都是先从某个点出发，求出以这个节点为根的答案，并记录与答案相关的数据到数组中。然后从节点出发，记录换根的答案，其中所有根的最大值就为所求值。难点在于该如何去找寻其中的递推关系式。数组表...

树换根dp DP

2020-04-17

0 642

NC201400

题意一棵个结点的树，令根节点的深度,其他节点的深度为，求以某个点为根节点这棵树的最小为多少？思路我们要枚举每一个结点为根节点的为多少，我们可以先求得以某片叶子为根节点的，然后再找寻相连的的关系，记录最小值。以某一片叶子为根节点，DFS遍历整棵树，算其深度，算该节点的子树结点数量为。(无根树很多...

dfs 树

2020-04-16

0 667

NC14248

NC14248 题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同思路 DFS 树数据结构这道题和CF1339D十分相像，有兴趣的可以做一下。把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树...

DFS 树数据结构

2020-04-14

2 774