标签:树上差分

【题解】bzoj4326/洛谷2680/codevs5440 运输计划 ——litble

题目描述

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 树上差分

1. 用途

首先是有根树。
我们需要实现如从点u到点v的(最短)路径上所有点的权值+1这种操作。
而且我们不需要频繁的求某个点的权值。

2. 实现方法

类似于前缀和的思想。
首先我们定义:val[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 运输计划 LCA+二分答案+树上差分 NOIP – 2015 LUOGU – 2680

1. 题目

传送门= ̄ω ̄=
题意,给你一棵无根树,再给你一些点对。你现在可以使树上某一条边的长度变为0,求给出的点对之间的路径中最长的那条路径最短为多长。
数据范围30W

2. 题解

我太菜了[......]

[继续阅读= ̄ω ̄=]

Read MoreComment