#include <iostream> #include <string> #include <map> #include <stack> #include <vector> #include <cstdlib> #include <stdio.h> using namespace std; string x[200005]; int weight[200005]; int segtree[200005][20]; string name[200005][20]; int mycount = 0, mleft = 0, mright = 0; map<string, int> last; template <class T> class Node{ /* * This is a Tree Node class. */ public: T field, parent; int depth; vector<T> son; Node(){ field = ""; depth = 0; son.clear(); parent = ""; } Node(T myfield){ field = myfield; depth = 0; son.clear(); parent = ""; } void add_child(T child){ son.push_back(child); } void set_parent(T sparent){ parent = sparent; } }; template <class T> class GenTree{ public: Node<T> *root; map<T, Node<T>* > nodes; GenTree(){} GenTree(T root_field){ root = new Node<T>(root_field); root->parent = root_field; nodes.insert(pair<T, Node<T>* >(root_field, root)); } Node<T>* add_node(T field, T parent = ""){ Node<T> *node = new Node<T>(field); nodes[field] = node; if (parent!= ""){ nodes[parent]->add_child(field); node->parent = parent; } else node->parent = field; return node; } void dfs(T field, int depth){ x[mycount++] = field; nodes[field]->depth = depth; int size = nodes[field]->son.size(); if (size != 0){ for (int i=0; i<size; i++){ T cur_son = nodes[field]->son[i]; dfs(cur_son, depth + 1); x[mycount++] = field; } } last[field] = mycount; } }; int cal_pow(int x, int y){ if (y == 1) return x; else if (y == 0) return 1; if (y % 2 == 0){ int temp_value = cal_pow(x, y/2); return temp_value * temp_value; } else{ int temp_value = cal_pow(x, (y-1)/2); return temp_value * temp_value * x; } } int findmax(int len){ int count = -1; while (len > 0){ count++; len = (len >> 1); } return count; } int main() { GenTree<string> mytree; int n, m, len, maxT, templen; string name1, name2, root; cin>>n; for (int i=0; i<n; i++){ cin>>name1>>name2; if (i==0){ root = name1; mytree.add_node(name1); mytree.add_node(name2, name1); } else mytree.add_node(name2, name1); } mytree.dfs(root, 1); for (int j=0; j<=findmax(2*n+1); j++) for (int i=1; i<=2*n+1; i++) { len = cal_pow(2, j); if (j == 0){ segtree[i][j] = mytree.nodes[x[i-1]]->depth; name[i][j] = x[i-1]; } else if ((i + len/2) <= (2*n+1)){ if (segtree[i][j-1] > segtree[i+len/2][j-1]){ segtree[i][j] = segtree[i+len/2][j-1]; name[i][j] = name[i+len/2][j-1]; }else{ segtree[i][j] = segtree[i][j-1]; name[i][j] = name[i][j-1]; } } } cin>>m; for (int i=0; i<m; i++){ cin>>name1>>name2; if (last[name1] > last[name2]){ mleft = last[name2]; mright = last[name1]; }else{ mleft = last[name1]; mright = last[name2]; } len = mright - mleft + 1; maxT = findmax(len); templen = cal_pow(2, maxT); if (segtree[mleft][maxT] > segtree[mright - templen + 1][maxT]) cout<<name[mright - templen + 1][maxT]<<endl; else cout<<name[mleft][maxT]<<endl; } return 0; }
相关推荐
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
改产品是一款测量水平的仪器,是一款军工产品
linux-conf-au-2019-epaper-badge:lca2019的我的IoT徽章
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
第4章 倍增求LCA-2019-12-05 第4章 倍增求LCA-2019-12-05 第4章 倍增求LCA-2019-12-05
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
LCA (Lobe Component Analysis) Lobe成分分析法,图像基元的特征检测算法。
本书的目标读者是准备去硅谷找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM算法竞赛的新手。 市场上讲解算法的书已经汗牛充栋,为什么还要写这本书呢?主要原因是我对目前市场上的大部分算法书都不太...
图论--LCA--树上倍增法(在线) 图论--LCA--在线RMQ ST 最小环: 图论--最小环--Floyd模板 树的直径: 图论--树的直径--DFS+树形DP模板 树的重心: 图论--树的重心(DFS) 模板 生成树: ...
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
LCA详解,内附算法、代码
Tarjan应用LCA
Tree_LCA---倍增
LCA词汇复杂度分析软件 跟官网一毛一样 可以做成本地接口
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
有不会的就来看看吧,希望能帮到大家
ACM 算法模板集 Contents 一. 常用函数与STL 二. 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...
LCA讲解,有图片与版题(含代码)帮助理解