标签:lca

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

题目描述

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

[继续阅读= ̄ω ̄=]

Read MoreComment

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

1. 题目

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

2. 题解

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

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】货车运输 codevs – 3287 倍增求lca

1. 题目

传送门= ̄ω ̄=

题目描述 Description

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】find the safest road HDU – 1596

1. 题目

传送门= ̄ω ̄=

problem

XX星球有很多城市,每个城市之间有一条或多条飞行通道,但是并不是所有的路都是很安全的,每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 倍增求LCA

1. 何谓LCA

LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

img

如图,1和7的公共祖先有5和10,而它们的LCA[......]

[继续阅读= ̄ω ̄=]

Read MoreComment