wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共9篇）

LCA

LCA LCA（Lowest CommonAncestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先一般采用倍增的方法来求最近公共祖先。还可以用树链剖分。dfs序似乎也可以思路用数组fa[i][j]表示从i往上跳2j步所得到的祖先。用dep[i]表示i的深...

最近公共祖先

2018-08-13

0 617

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 378

[luogu2420][让我们异或吧]

luogu2420 思路: 非常裸的一道lca的题，维护一个lca数组，一个异或数组，然后在找lca的过程中。进行异或即可。代码： #include<cstdio> #include<iostream> using namespace std; const int ...

最近公共祖先

2018-09-27

0 409

[luogu3398][仓鼠找sugar]

luogu3398 思路: 假设松鼠a要从a1去a2,松鼠b要从b1去b2，ks表示lca(a1,a2)和lca(b1,b2)中深度较深的那个。那么，若要使得两只松鼠可能相遇，则只要满足lca(a1,b1)，lca(a1,b2),lca(a2,b1),lca(a2,b2)中任意一个的深度深于ks...

最近公共祖先

2018-09-27

0 491

LCA

LCA LCA（Lowest CommonAncestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先一般采用倍增的方法来求最近公共祖先。还可以用树链剖分。dfs序似乎也可以思路用数组fa[i][j]表示从i往上跳2j步所得到的祖先。用dep[i]表示i的深...

最近公共祖先

2018-08-13

0 378

[luogu1967][货车运输]

题目链接题意：其实题目的意思就是问从x到y权值最小的路的权值最大能是多少。思路：首先可以先把这张图变成一棵树。因为那些更小的点肯定是不跑更优秀，而且题目没有要求路程，所以生成一棵树，只要能保证在同一个图里面的点能够连通即可。又因为他要使最小权值最大，所以可以只留下那些权值更大的边。所...

最近公共祖先最小生成树

2018-08-21

0 467

[luogu2420][让我们异或吧]

luogu2420 思路: 非常裸的一道lca的题，维护一个lca数组，一个异或数组，然后在找lca的过程中。进行异或即可。代码： #include<cstdio> #include<iostream> using namespace std; const int ...

最近公共祖先

2018-09-27

0 440

[luogu3398][仓鼠找sugar]

luogu3398 思路: 假设松鼠a要从a1去a2,松鼠b要从b1去b2，ks表示lca(a1,a2)和lca(b1,b2)中深度较深的那个。那么，若要使得两只松鼠可能相遇，则只要满足lca(a1,b1)，lca(a1,b2),lca(a2,b1),lca(a2,b2)中任意一个的深度深于ks...

最近公共祖先

2018-09-27

0 456

luogu4211 LCA

题目链接思路我们换一种求\(dep[lca(i,j)]\)的方法。将从根到\(i\)的路径上所有点的权值加\(1\)，然后求从根节点到j路径上点的权值和。就是\(i\)和\(j\)的\(lca\)的深度。以此类推，对于求\(\sum\limits_{i=l}^rdep[lca(i,z)]...

最近公共祖先线段树树链剖分

2019-01-29

0 522