hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共5篇）

Max Flow 来自专栏

题意：有一颗n个节点的树，有k次操作，每次操作给出二个节点，然后将二个节点及二个节点之间的节点权值都加一，然后求最后树中权值最大的节点的权值为多少？思路：lca+差分：用lca求出二个节点u、v的最近公共祖先k，k的父亲节点为kp；要使u、v路经上节点权值加一则val[u]、val[v]进行加一，...

LCA 树上差分

2021-04-19

0 839

[AHOI2008]MEET 紧急集合来自专栏

题意：有一颗n个节点的树，现在有m个询问，每个询问给与三个节点，求这三个节点在哪个节点集合时总距离最小？输出集合节点和总距离。思路：我们知道在树上求任意两个节点可以用lca求取，求三个节点怎么转换成求两个节点呢，我们画一颗树然后任找三个点可以发现两两之间的lca的值要么三个相等，此时该点为集合点，...

LCA

2020-11-26

3 801

小A的最短路

题意：有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？思路：求任意两点树上的距离应该用LCA.由于多了个电缆，所以我们从x到y是有3种方案：①从x直接到y，不坐电缆。②从x到u，再从u坐电缆...

LCA

2020-08-09

1 647

Alliances

题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？思路：在树...

dfs 二分 LCA

2020-07-11

1 701

最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小...

最短路并查集 LCA

2020-07-08

0 684