distance
[ABC294G] Distance Queries on a Tree 题解
## Description 有一个节点数为 $N$ 的树。边 $i$ 连接 $u_i$ 和 $v_i$，边的权值为 $w_i$。 $Q$ 次询问，询问一共有两种。 ```1 i w``` ：改变第 $i$ 条边的权值为 $w$。 ```2 u v``` ：输出 $u$ 到 $v$ 的路径距离。 数 ......
「解题报告」ARC103D Distance Sums
给 Kaguya 看了一眼，Kaguya 用了一分钟切了。我看了一个小时。这就是神吗。 考虑一个点往叶子走答案的贡献，显然距离和会变化 $-siz_u + (n - siz_u) = n - 2siz_u$。如果我们以重心为根，那么所有的 $n - 2siz_u > 0$，那么这实际上是一个小根堆。 ......
Prime Distance UVA - 10140
定两个整数 L,R , 求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。 当存在多个时，输出靠前的素数对。 筛 1e6 每个素数，在区间里标记倍数 #include<iostream> #include <algorithm> #include <cstring> using n ......
abc253_e Distance Sequence 题解
题目传送门 简单的动态规划题。 绝对详细！ 题意 给定三个整数 $n$、$m$ 和 $k$，求有多少个序列满足以下条件： 对于 $1 \leqslant i \leqslant n$，$1 \leqslant a_i \leqslant m$。 对于 $1 < i \leqslant n$，$\le ......
[ABC127E] Cell Distance
2023-01-08 题目传送门 翻译 难度&重要性(1~10):1 题目来源 AtCoder 题目算法 dp,逆元 解题思路 转化一下，分离行列，针对每一对去计算方案。 以下以行为例子。 考虑两个之间行距为 $i$，都可以随便选择一列，从 $n-i$ 个行距为 $i$ 的行组合中挑选一个，然后再选 ......
Gym104076L Tree Distance
Gym104076L Tree Distance 题目链接。 $\text{difficulty}={4,2.5}$。 $\text{tags}=点分治,扫描线$。 没见过确实想不到。 由于查询是区间对区间，分块等数据结构并不好直接维护。考虑找一些性质，如果两个点 $l,r(l <r)$ 的距离大于 ......
题解 ABC294G【Distance Queries on a Tree】
DFS 序树状数组。 不妨以 $1$ 为根，设 $\operatorname{dep}(u)$ 表示 $u$ 到根路径的边权和，$\operatorname{dis}(u,v)$ 表示 $u,v$ 间路径的边权和，$\operatorname{LCA}(u,v)$ 表示 $u,v$ 的最近公共祖先。 ......