shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

Alliances 来自专栏

前言: 这个每日一题对我来说稍微复杂了亿点点... 思路: 首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离. 假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离. 假如不是,那么V一定位于LCA的子树中.这是我...

dfs 二分 LCA

2021-01-22

2 841

MMSet2 来自专栏

将求树的直径的过程进行模拟即可~ #include <bits/stdc++.h> using namespace std; const int N=3e5+50,M=20; vector<int>v[N]; int dep[N],w[N],f[N][M]; void dfs...

LCA 证明

2021-01-21

1 798

Exercise Route 来自专栏

很难的一个题目(对我这种图论蒟蒻来说).首先你得会的算法有:lca,dfs(居然没了...这个题的解法分为三步:1.转化题意:原本的题意是给你n个点,m条边,前n-1条是树边,后面的边和树边可以形成多少个环?->成环可以转化为,a->b的路径和c->d的路径有交集.我们去掉交集就是...

LCA DFS 图论

2020-09-11

1 626