DaMing

分类

题解(25)

/ 注册

全部文章（共2篇）

最短路-（生成树+最短路+LCA）

题目描述n 个点，m条边， q个询问，每次输出 x,y的最短距离思路首先看一个弱化版的给你n个点，n-1条边构成一颗树，q个询问，每次输出树上两点x,y的距离这个题就是一个裸的LCA，lca的dfs完之后可以直接输出 int dis(int x, int y) { return de...

DFS 最短路 LCA

2020-07-08

2 878

漂亮的公园(LCA+思维)

题目描述一棵树，每个节点有一个颜色，q个询问每次询问x，y求树上距离最长的两点其中一点color【i】=x;另外一点color【i】=y；思路1.对于求树上两点之间的距离可以用lca，倍增法求lca也不再介绍2.求max(color[i],color[j]]如果只看一种颜色x求最长的距离可以枚举是x...

LCA 离散化

2020-06-05

0 782