Source
Codeforces Round #362 (Div. 2)
My Solution
LCA(最近公共祖先) 在有根树中,找出某两个结点u和v最近的公共祖先(或者说,离树根最远的公共祖先)。
类似于这样来访问
inline int LCA(const int &u, const int &v)
{
while (u != v){
if(u < v){ //if(v < u){
swap(u, v);
}
u = u/2; // v/2 is parent of vertex v
}
return u;
}
每次修改的时候直接修改就行
1e18 -> 2^63次所以每次 2*63*q == 1e5
复杂度 O(2*63*n)
此外对于 map<pair<LL, LL>, LL> mpt;//map tree
和 map<LL, map<LL, LL> > mpt;//map tree
前面用 Codeforces上的数据做了测试, 这两种写法时间上是差不多的, 然而在空间复杂度上 前者是后者的一半
所以以后就用map<pair<LL, LL>, LL> mpt;//map tree 来处理 1<= u, v <= 1e18, w 这样节点标号很大的情况好了
如果时间压的比较紧可能可以尝试用
FF 计算机... 柱爷
离散化
vector<pair<int,int>> G[N]
读完后sort每个G[i]
后面二分找
#include
#include
#include
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/codeforces-round-362-div-2-c-lorenzo-von-matterhorn-lca/
共有 0 条评论