之前是不是从来没发过数据结构的笔记之类的？那是因为我数据结构太菜了，这几天狂刷数据结构题！ 模板 - 树状数组1 支持单点修改，并查询区间和的问题。 最经典的树状数组模板题，这里讲解一下如何操作。 树状数组其实维护的是前缀和，而两个前缀和相减就是区间和。 lowbit 求出该数最后一个1的位置。式子是 $x \And -x$。 线段树有一个底层，这…

T1.简单树（easy.cpp） 题目描述 给定一棵 $n$ 个点的树，你需要给每条边赋值 $0$ 或 $1$，求树上所有点对之间的简单路径权值总和的最大值，并输出方案。 一条路径的权值定义为这条路径上所有边权的异或和。 题解 引理 可以知道， $ans(x,y) = ans(x, root) \oplus ans(y, root)$。将树想象成一…

题目描述 给定 $n$ 和 $k$ 棵有 $n$ 个点的树。对于每个点对 $(i,j)$ ，求出其在每棵树上的路径经过的点（含端点）的交集大小。 数据范围: $1 \leq n, k \leq 500$ 时间限制: $2.000s$ 题解 首先明白一个性质：对于某一棵树，考虑 $x$ 在 $(u, v)$ 路径上的充要条件：$dis(u,x) + …

问题描述 给定一个 $n$ 行 $m$ 列的网格图，每个格子的颜色是蓝色、白色中的一种。白色的格子是障碍点。对于 $2$ 个有公共边的蓝色格子，它们之间是连通的。保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。现给出 $Q$ 个矩形区域，对每个矩形区域求出对蓝色格子来说的连通块个数（不能经过白色格子和矩形区域外的格子）。 数…

[题目链接] Lomsat gelral [原题链接] E. Lomsat gelral Lomsat gelral 题面翻译 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子…

2. 摘 Galo(OvO) 1s/512M [XOJ]仅评测链接 2.1 题目描述： 0v0 在野外看到了一棵 Galo 树，看到食物的 0v0 瞪大了眼睛，变成了 OvO 。 这棵 Galo 树可以看做是一棵以 $1$ 号点为根的$n$个点的有根树，除了根节点 以外，每个节点i都有一个 Galo ，美味度为$w[i]$。 OvO…