树上专题
【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】
传送门：【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE，FFT跑的超级快…… my code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m
F. LIS on Tree 树上根路径LIS
1 关于lower_bound // 12345 查4 应该放在4 。而不是5的位置。。所以不是uppper。 //如果1235 查4 。可以优化5 。 2 关于 ans[u] = max(j, ans[p]); 维护一个max 一定从（premax，cur)中选出来的。 3 关于 memset(st, 0x3f, sizeof st); 这个和st + 1, st + n + 1 。。我们二分选
HDU 5016 Mart Master II (树上点分治)
题目地址：HDU 5016 先两遍DFS预处理出每个点距最近的基站的距离与基站的编号。 然后找重心，求出每个点距重心的距离，然后根据dis[x]+dis[y] < d[y]，用二分找出当前子树中不会被占领的数量，总点数减去即是被占领的数量。这样就可以求出每个点最多占领的点的数量。然后找最大值即可。 代码如下： #include <iostream>#include <string.h>
HDU 4871 Shortest-path tree (最短路+树上点分治)
题目地址：HDU 4871 先用最短路求出根节点到其它各点的最短距离，然后利用最短距离DFS一下构造出最短路树，然后剩下的就是在构造出来的这棵树上做树分治，很简单的树分治。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include
SPOJ 1825 FTOUR2 - Free tour II (树上点分治)
题目地址：SPOJ 1825 树分治的题果然除了模板题就是金牌题啊。。。这题是一道论文题，想了好长时间。。。。终于过了，，，，注意一个坑点，如果权值全部为负的话，是可以不选任意一条边的，这样权值为0。。。也就是说初始值要设为0。。。 具体看漆子超的论文《分治算法在树的路径问题中的应用》。。 代码如下： #include <iostream>#include <string.h>#inc
BZOJ 2152 聪聪可可 (树上点分治)
题目地址：BZOJ 2152 找有多少对权值和为3的倍数的点。最简单的点分治。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#incl
POJ 2114 Boatherds (树上点分治)
题目地址：POJ 2114 点分治水题。只是把距离小于等于k改成了等于k。稍微加一点处理就可以了。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <
POJ 1741 Tree (树上点分治)（楼教主男人八题之一）
题目地址：POJ 1741 树分治第一发！ 树分治详情请看漆子超的国家集训队论文，论文传送门 树分治裸题。 代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#inc
最近公共祖先（LCA），树上差分，树的直径总结
最近也是一不小心就学到了树论，这方面确实太不行了，也该开始学习一下了，那么话不多说，进入今日份的树论学习，直接开冲 最近公共祖先（LCA）——倍增思想（可以结合我之前写的ST表学习） 我们来看什么是最近公共祖先，对于9和8来讲，其最近公共祖先为6，对于3和7来讲，其最近公共祖先为5，那么我们去求最近公共祖先总共要有两步 第一步就是深搜，我们这一遍的深搜主要是为了去统计每一个点的深度
hdu 2586 树上点对最近距离 （lca）
,只要知道dis[i][j]=dis[i][root]+dis[j][root]-2*dis[Lca(i,j)][root]. 其中root为树的根节点，LCA(i,j)为i,j的最近公共祖先。 所以我们先把所有的询问储存下来，然后离线直接查询。复杂度是o(n+q)的。 VIE #include<cstdio>#include<algorithm>#include<i
LibreOJ #10131. 「一本通 4.4 例 2」暗的连锁 题解 树上差分
暗的连锁 题目描述 Dark 是一张无向图，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 N−1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 M 条附加边。 你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark
hdu2545 树上战争 (并查集)
Problem Description 给一棵树，如果树上的某个节点被某个人占据，则它的所有儿子都被占据，lxh和pfz初始时分别站在两个节点上，谁当前所在的点被另一个人占据，他就输了比赛，问谁能获胜 Input 输入包含多组数据 每组第一行包含两个数N，M（N，M<=100000），N表示树的节点数，M表示询问数，N=M=0表示输入结束。节点的编号为1到N。 接下
大话数据结构读书笔记系列（六）树上篇
转载请注明出处：http://blog.csdn.net/u010194538/article/details/51212759 这章内容比较多，分为上和下2篇： 第6章树 6.2 树的定义 之前我们一直在谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构——“树”。 树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一
树上问题（一）倍增算法求最近公共祖先
倍增算法求最近公共祖先 一、概述 在图论和计算机科学中，最近公共祖先 LCA(Least Common Ancestors)是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。 --维基百科 上图中， L C A ( 11 , 8 ) = 8 LCA(11, 8)=8 LC
在2-3-4树上实现连接与分裂操作的算法与实现
在2-3-4树上实现连接与分裂操作的算法与实现 引言1. 维护2-3-4树结点的高度属性伪代码示例 2. 实现连接操作伪代码示例 3. 证明简单路径p的划分性质4. 实现分裂操作伪代码示例 C代码示例结论 引言 2-3-4树是一种平衡搜索树，它保证了树的高度被有效控制，从而为查找、插入和删除操作提供了较好的时间复杂度。在本篇文章中，我们将探讨如何在2-3-4树上实现连接与分裂操作
968.监控二叉树 树上最小支配集
法一: 动态规划 一个被支配的节点只会有三种状态 1.它本身有摄像头 2.他没有摄像头, 但是它的父节点有摄像头 3.他没有摄像头, 但是它的子节点有摄像头 我们 dfs(node,state) 记录在node节点时(以node为根的子树),状态为state下的所有最小摄像头 // 本身有摄像头就看左右孩子了 dfs(node,1
CCF-CSP真题《202312-3 树上搜索》思路+c++满分题解
想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全 问题描述 试题编号：202312-3试题名称：树上搜索时间限制：1.0s内存限制：512.0MB问题描述： 题目背景 问题描述 输入格式 输出格式 样例1输入 5 2 10 50 10 10 20 1 1 3 3 5 3 样例1输出 2 5 2 5 3 4 样例解释 子任务 真题来源：树上搜
BZOJ 4033. [HAOI2015]树上染色（树形DP，边贡献）
Description 有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并 将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 Input 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。 输入保
树上启发式合并（dsu on tree）学习
声明：本文部分内容摘自OI Wiki网站。详情可自行查看学习。 洛谷 P9233 题目实际上是蓝桥杯 2023 年 A 组省赛的一道题。题干大致的意思是，给定一个含有 n n n 个结点，并且以 1 1 1 为根的一棵树，每个节点 i i i 都有一个颜色 C i C_i Ci，问这棵树有多少个子树是颜色平衡树。其中，如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是
POJ - 2486 :Apple Tree 树上有依赖背包
传送门 题目描述 一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走k步，最多能遍历到的权值。 分析 首先我们可以去dfs每一个为为根节点的时候，子树走 k k k步的时候的最大权值，但这里涉及到一位问题，因为每一条边可以重复走，所以会不会有回头的情况 我们用 f [ i ] [ j ] [ 0 / 1 ] f[i][j][0/1] f[i][j][0/1]表示在 i
CodeForces 815C :Karen and Supermarket 树上有依赖背包
传送门 题目描述 在回家的路上，凯伦决定到超市停下来买一些杂货。 她需要买很多东西，但因为她是学生，所以她的预算仍然很有限。 事实上，她只花了 b b b美元。 超市出售 N N N种商品。第 i i i件商品可以以 c i c_{i} ci美元的价格购买。当然，每件商品只能买一次。 最近，超市一直在努力促销。凯伦作为一个忠实的客户，收到了 n n n张优惠券。 如果凯伦购买 i i i次商
The more, The Better 树上背包
传送门 题目描述 ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？ 分析 树上背包问题，建立一个虚根即可 代码 #pragma GCC optimiz
每周一算法：树上差分
题目链接 闇の連鎖 题目描述 传说中的暗之连锁被人们称为Dark。 Dark是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。 经过研究，你发现Dark呈现无向图的结构，图中有 N N N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。 Dark 有 N – 1 N–1 N–1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。 另外，Dark
nefu 1330 树上计算 (dfs序+树状数组)
树上计算 Problem:1330 Time Limit:1000ms Memory Limit:65535K Description 给出一棵以 1 为根的树，初始每个顶点的权值为 0 。现有两种操作: 1 x 代表将顶点 x 的权值加一 2 x 询问顶点 x 的子树（包含x本身）的权值和是多少 Input 第一行样例个数