树上差分

虚树+ DP + 树剖 + 二维数点 题意： 给一棵树，每个点有一个颜色，多次查询给定 \(x,d\),询问树上距离某个点 \(x\) 小于等于 \(d\) 的所有点的颜色个数，这些点显然形成一个连通块。 先将询问离线，考虑对于每个点，求出每个颜色对这个点的最小距离，考虑二维数点，来计算出 \(\l ......

P2664 树上游戏 解法一：淀粉的另一种形式。 正常淀粉求得是每条路径，此题要求每个点为端点的所有路径，所以处理当前连通块时不仅要考虑根的答案，也要考虑根的子树对另一棵子树的影响。 解法二：考虑颜色的贡献。 跳出对点的答案的计算，思考每种颜色分别的贡献。对于每种颜色，\(i\) 对于 \(j\) ......

在树上，对于每个点 \(u\) ，设 \(c(u)\) 为点对 \((s, t)\) 的数量，满足 \(s \ne t\) ，且 \(s\) 到 \(t\) 的路径经过点 \(u\) 。 要求用总共 \(\mathcal O(n)\) 的复杂度，求出 \(c\) 数组。 我们可以把要求的 \(c(u ......

最短路 Floyd 多源最短路径 引入 Floyd 利用了 dp 的思想，主要可以用来求任意两个节点的连通性或最短路，可以有负边权，但不能有负环。 例题：luogu B3647 【模板】Floyd 我们设 \(f_{k,i,j}\) 为除了 \(i\) 和 \(j\) 外只经过前 \(k\) 个结点 ......

思路 : 找各种性质 1 每一秒只有 史莱姆进入起始点 , 然后他会选一个方向走(右或者下), 每一秒 史莱姆都会这样走 在考虑 前 t 秒内 有S个史莱姆到达这个点, 然后就会 有 s+1/2 个 往右走, s/2 往下走 而且 问t秒 只会 有 t-n-m-1 秒后的时刻影响 (诈骗t ) 于是 ......

突然来的感想： 如果求两个变量差的最大值，所有不等式变成"<="的形式跑最短路 如果求两个变量差的最小值，所有不等式变成">="的形式跑最长路 ......

原题 曾经会过 对于 \(x_i - x_j \leq k\) ，我们发现长得很像最短路/最长路的形式，因此我们可以抽象建图 建一个超级源点连向所有点，从超级原点跑最短路算法，跑出来的 \(dis_i\) 即对应 \(x_i\) 的一个解 前文提到过，差分约束问题可以转化为最短路或最长路问题，所以两 ......

P7624 令 \(d_i\) 表示 \(1\) 号车站到 \(i\) 号车站的距离，\(len\) 表示环形地铁的总长度。 考虑题中给的条件： \(type_i = 0\) 时，若 \(u_i < v_i\)，即可表示为 \(d_{v_i} - d_{u_i} \ge L_i \iff d_{u_ ......

P8201 简单题。 题中求的是 \(dis_{a, t} \oplus dis_{t, b} = k\) 是否存在，显然不好直接维护，考虑转化。 令 \(dist = dis_{a, t} \oplus dis_{t, b}\)，\(val = \bigoplus\limits_{x\in \te ......

反思 树上LIS 题目描述 给你一棵 n个节点的树，树的每个节点上都有一个值 a[i] 。 现在要您求出从 1 号点到 i 号点的最短路径上最长上升子序列的长度。 就是单调栈优化+dfs回溯 对比两段代码的dfs部分: //AC Code inline void dfs(int u,int f){ ......

SDU Open 2023-F、树上随机游走 题目：https://codeforces.com/group/2altttv8oU/contest/477604/problem/F 题意：给定一棵 \(n\) 个点的无根树，在树上随机游走（即每次会从当前点等概率地走到一个相邻结点），\(q\) 次询 ......

还是复习笔记，因为我发现我都不会 数组 \(a=[1,9,1,9,4,5,1,4].\) 前缀和 前缀和数组 \(s = [1,10,11,20,24,29,30,34]\). 如何计算？ \(s_i = s_{i - 1} + a_i\)。 有什么用？ 计算区间和，区间 \([l,r]\) 的和就 ......

一般的差分用于对一段区间进行加减，但如果在该区间内加减的是一段等差数列呢？ 对于一段区间 [l,r], 加一段首项为 s, 末项为 e 的等差数列。其公差 d=(s-e)/(r-l+1) 为简化问题讨论，先假设这段区间都为 0。 原数组：0 0 0 0 0 0 0 添加后的数组：0 0 4 6 8 ......

Part1 定义 可简单理解为前缀和的逆运算 Part2 实现 定义 \(a\) 数组为 \(f\) 数组的前缀和，则 \(f\) 数组为 \(a\) 数组的差分数组，则有 \[a_i = \sum_{j=1}^{i} f_j = f_1 + f_2 + \cdots + f_i \]\[f_i=\ ......

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode ......

描述 给出 n 个点的一棵树，多次询问两点之间的最短距离。注意：边是双向的。 输入描述 第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；再接下来 m 行，每行两个整数 x,y，表示询问点 x 到 ......

P5659 [CSP-S2019] 树上的数 前言 被队友（大爹）易giegie要求做这道题，一天一夜绞尽脑汁终于写出来了。（下了样例test1调试） 然后被要求写博客 虽然我觉得没啥用，但是写一下吧 一些说明 1.把数在删边时交换的过程看做移动，停留过的点和相关的边认为是经过这些点和边 2.把一条 ......

1、一维差分 首先要知道，差分是前缀和的逆运算， a1 a2 …… an 前缀和b1 b2 …… bn 差分 以AcWing.797为例，题目要求如下： 输入一个长度为 n 的整数序列。 接下来输入 m 个操作，每个操作包含三个整数 l, r, c ，表示将序列中 [l,r] 之间的每个数加上 c ......

链接：https://ac.nowcoder.com/acm/contest/64384/C 来源：牛客网 超市里一共有 \(n\) 个货架，\(m\) 个商品，一开始商品的位置是被打乱的，小Why需要将商品全部归位。 小Why在给货架编号后，实现了每个商品所在货架必然在其应在货架之前。 小Why决 ......

题目链接：https://www.acwing.com/problem/content/description/395/ 解题思路： 差分约束。 为了方便起见，定义第 \(i\) 个时间段为 \(i-1:00\) 到 \(i:00\) 这个时间段。 首先，为了方便开一个额外的点，令 \(R_i\) ......

一个博客需要一份头图： 强制在线（论一个 ^ 引起的癫狂： P6177 Count on a tree II/【模板】树分块 题意： 给定一棵树，每个节点有颜色。 每次询问一条路径上不同颜色的个数，强制在线。 数据范围 \(1 \leq n \leq 4\times 10^4,1\leq m \le ......

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode ......

一家公司里有 n 个员工，他们的编号分别是 1 到 n ，其中 1 号员工是公司 CEO，CEO 在公司里没有上司。除了 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。i 号员工来参加舞会会为大家带来 ai 点快乐值。由于场 ......

1.前缀和 一维数组 #include<iostream> using namespace std; const int N=1e5+10; int main() { int n,m,a[N],sum[N]={0}; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++ ......

倍增表又称ST表，是一种离线算法，不支持修改，在离线算法中，复杂度非常快，代码简洁实用 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const int N = (1<<13)+39+7; int n,m, ......

Poisson equation can be writtern as follows: \[\nabla\cdot[\epsilon(r)\nabla\phi(r)] = -q(p-n+N_D-N_A)\\ \nabla\epsilon(r)\cdot\nabla\phi(r) + \epsilo ......

[USACO12FEB] Nearby Cows G 题目描述 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 输入格式 第一行两个正整数 \(n,k\)。 接下来 \(n-1\) 行，每行两个正整数 \(u,v\)，表示 \(u ......

[CTSC1997] 选课 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 \(N\) 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学 ......

【题解】[ABC318G] Typical Path Problem 题目链接 G - Typical Path Problem 题意概述 给定一个 \(n\) 个点 \(m\) 条边的无向连通图。 给定三个该图上的不同顶点 \(A,B,C\)，问是否存在一条从 \(A\) 到 \(C\) 的简单路 ......

1 `timescale 1ns / 1ps 2 ////////////////////////////////////////////////////////////////////////////////// 3 // Company: 4 // Engineer: 5 // 6 // Cre ......