tree
ARC121E Directed Tree
ARC121E Directed Tree 有意思的容斥加树 dp。 思路 \(a_i\) 可以是除去 \(i\) 祖先之外的所有点，考虑 \(a_i\) 的逆排列。 每一个 \(i\) 在正排列里都可以被不是自己子树内的点选择，那么逆排列里 \(i\) 不可以放自己子树内的点（不包括自己）。 现在 ......
[ARC121F] Logical Operations on Tree 题解
题目链接 点击打开链接 题目解法 比较好的题 首先要发现一个性质是：先删 AND 边，再删 OR 边最优 小证一下：分类讨论 AND 边两端的数字情况 \(0 \& 0\) 左右两端虽然可能可以把 \(1\) OR 过来，但这种情况先做 \(\&\)，也一定可以 OR 得到 \(1\) \(0 \& ......
【题解】CodeForces 1902F Trees and XOR Queries Again
传送门：https://codeforces.com/contest/1902/problem/F 数据结构题，这里讲两种思路。 $ST$ 表思路： 判定“从若干个数中能否取出其中一些，使得异或和为 $x$”的问题，第一时间想到线性基，本题要做的显然就是快速求出询问路径上所有数的线性基。两组数的线性 ......
F. Trees and XOR Queries Again
首先容易想到lca+线性基，\(O(nlognB^2+qlognB^2)\)，显然T飞了。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vector> #i ......
【题解】Trees and XOR Queries Again - Codeforces 1902F
https://codeforces.com/contest/1902/problem/F 方法一 可以从树上路径想到轻重链剖分（也可以用其他种类的LCA算法），然后从数的异或表示很容易想到线性基。 然后因为是无修改的，所以可以轻重链剖分+ST表+线性基。具体来说就是： 先进行轻重链剖分。然后把每次 ......
Top Tree 学习笔记
前言 学了一周才学会... 本来是照着 OI Wiki 上的 SATT 写的，后来看到一半感觉自己懂了然后写了自己理解的版本。看题解后发现这个版本像 AAAT，于是我也不知道它应该叫 AAAT 还是 SATT 了。且叫它 AAAT 吧。 贺一张 lxl 的图： 正文 我理解的 AAAT 是维护子树的 ......
Top Tree 模板（咕）
Sone1 调不动了，所以是 lg P3690。 写着写着就不知道自己写的是 AAAT 还是 SATT 了，反正能用。 #include <iostream> #include <vector> #include <cassert> #define UP(i,s,e) for(auto i=s; i ......
P9665 [ICPC2021 Macao R] Colorful Tree 题解
我永远喜欢数据结构。 题目传送门 给出一棵树，初始只有一个点 \(1\)，其颜色为 \(C\)。 有 \(q\) 次操作，分为两种类型： \(0\space x\space c\space d\)，记当前树中一共有 \(n\) 个点，新增一个 \(n+1\)，其父亲为 \(x\)，颜色为 \(c\) ......
[AGC052B] Tree Edges XOR 题解
题目链接 点击打开链接 题目解法 怎么感觉这场 \(B\) 比 \(C\) 思维量更大 考虑一步很妙的操作：把边权变成点权，以达到简化操作的目的 使每条边的边权为两端点的异或和，手画一下可以发现，操作简化成了交换两端点的点权 我们定义 \(d_{1/2,i}\) 定义为在 \(1/2\) 树上，\( ......
el-tree筛选时保留父节点和子节点
watch: { filterText(val) { console.log('val', val); this.$refs.tree.filter(val); } }, methods： // 筛选 filterNode(value, data, node) { if (!value) retur ......
ICPC2022Xian L Tree 题解
Link ICPC2022Xian L Tree Question 给出一个根为 \(1\) 的树，需要将树分成几个块每个块，一个块中的节点需要满足以下条件中的一个： 对于所有的 \(u,v \in S,\ u \neq v\) ，满足 \(u \in subtree(v)\) 或 \(v \in ......
如何动态展开el-tree的某个子节点
需求： 当添加文件夹或者表单时展开该节点 addChildDirectory(node, data) { this.$nextTick(() => { // 重命名时展开改文件夹 this.$refs.tree.store.nodesMap[data.id].expanded = true; }); ......
CF1901E Compressed Tree（树dp）
Problem 题目地址 Solution 来自fcy大佬的思路 记 \(f_u\) 表示假定以 \(u\) 为根的子树，在压缩后，（子树内的某一个点（包括 \(u\)））可以向外（除\(u\)为根的子树外所以点的集合）连一条边时的最大 \(sum\)。换言之，我们把树拆成 以\(u\)为根的子树（ ......
[ABC321E] Complete Binary Tree
思路：第一次先把往后距离为 $k$ 的点算出来，然后再每次往前走一个，考虑 $k-i$ 的情况。（具体见代码注释）。 代码： ```cpp#include <bits/stdc++.h>using namespace std;// headint sum[100],head=0;int n,x,k; ......
CF1900 C Anji's Binary Tree 题解
Link CF1900 C Anji's Binary Tree Question 给出一个树，每个节点上有一个字母 L/R/U ，从 \(1\) 号根节点开始，L 表示接下来走到左节点，R 表示接下来走到右节点，U 表示接下载走到父节点 问，最少修改几个节点上的字母使得从根节点走到叶子节点 Sol ......
Top Tree
总归要学的。 先写一下理解比较困难的点。 考虑 SATT 的建立过程：首先在树里面找到一个Compress Tree，这个树满足中序遍历写下来是根簇路径深度从小到大排列，然后根簇路径上挂着的小簇Rake起来，这个 Rake 的过程是容易的，考虑对于每一个直接连接的小簇，把他变成子问题，然后给一个代表 ......
从一次前端公共库的搭建中，深入谈谈tree shaking相关问题
项目背景 随着业务的积累，前端项目之间逐渐会产生许多可以跨项目复用的逻辑或组件。比如对前端数据库 indexedDB 的封装、对 fetch 请求进度和中断请求功能的扩展、以及可能会在多个项目使用的 react 和 vue 组件。当前已经有一个公共库专门用来收敛 js 的逻辑复用，但是随着相同技术栈 ......
CF1891 F A Growing Tree 题解
Link CF1891 F A Growing Tree Question 给出了一棵树，初始只有根节点，编号为 \(1\) 现在有两个操作 第一个操作：1 x 添加一个新节点 \(size+1\) ，这个新节点的父亲为 \(x\) 第二个操作 : 1 x val 给 \(x\) 的子树都加上 \( ......
kd-tree
k dimensional tree 用途 用于多维空间的搜索查询 (比如地图地理空间, 甚至搜索引擎多属性) 本质上是一颗二叉树, 里面的每个节点代表了一个矩形区域的切割 复杂度 首先平衡和不平衡的kdtree复杂度不一样, 不平衡的kdtree指的是所有的点都在同一侧, 以至于复杂度退化到了O( ......
JavaSE-父子id集合构建为树tree结构-示例
public class Node { private final Type type; private final List<Node> children; public Node(Type type) { this.type = type; this.children = new ArrayLi ......
【数学】Matrix-Tree 定理
题目描述 给定一张 \(n\) 个结点 \(m\) 条边的带权图（可能为无向图，可能为有向图）。 定义其一个生成树 \(T\) 的权值为 \(T\) 中所有边权的乘积。 求其所有不同生成树的权值之和，对 \(10^9+7\) 取模。 注意： 本题中，有向图的生成树指的是 以 \(1\) 为根的外向树 ......
[LeetCode] 1361. Validate Binary Tree Nodes 验证二叉树
You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the ......
23 MSTP概述（Multiple Spanning Tree Protocol/多生成树协议）
在划分VLAN的网络中运行RSTP/STP，局域网内所有的VLAN公用一棵树，被阻塞的链路不承担任何流量，无法在VLAN间实现数据流量的负载均衡，导致链路带宽利用率和设备利用率低，为了你部此缺点在802.1S定义了MSTP（Multiple Spanning Tree Protocol） MSTP概 ......
了解tree shaking
前言 前端在做性能优化的时候，其中一种有效的方式就是减少包体积的大小。而减少包体积大小的其中一种有效的方式就是 tree-shaking，翻译成中文就是摇树。这个词非常形象，当果树结果后，如果用力摇树，那些成熟了但是还挂在树上的果子就会掉下来，减轻树的负担，因为果子已经成熟了，没有必要在呆在树上了。 ......
使用 ABAP 代码构造 Merkle树（Merkle Tree）
源代码如下： *& * *& Report ZBLOCKTREE *& * *& *& * REPORT zblocktree. PARAMETERS: leafnode TYPE i. TYPES: BEGIN OF ty_merkletree, leafvalue TYPE string, le ......
CART（Classification and Regression Trees）
CART（Classification and Regression Trees）是一种常用的决策树算法，既可以用于分类问题，也可以用于回归问题。CART算法由Breiman等人于1984年提出，是一种基于递归二分划分的贪婪算法。以下是对CART算法的详细解释： 1. 决策树的构建过程： CART算 ......
Solution - Hossam and (sub-)palindromic tree
又名：《最近 vjudge 题全部罚坐》。 唯一 Trick：回文序列，就想区间 dp！时间复杂度 \(O(n ^ 2)\)！ 如果是序列：\(f_{l, r}\) 表示 \([l, r]\) 的最长回文子序列，\(f_{l, r} = \max(f_{l + 1, r}, f_{l, r - 1} ......
Tree MST 题解
洛谷 AT 完全图的最小生成树是不好求的，但是发现 \(\mathcal{O}(n^2)\) 级别的边中显然有很多都是没有用的，这种时候可以考虑分治。 显然如果对 \(E'(E'\in E)\) 求 MST，没有选择的边一定也不在最后的 MST 的边集中。于是就让选出的边集的并等于原图，然后再求一遍 ......