题目连接
题目大意
就是一棵树求任意两个节点的最近公共祖先。
算法描述
在题目的提示里面有比较详细的解释。这里就不多说了。这种算法的时间复杂度是O(n+q)。 在算法的实现上也有一些技巧，，在参考了一些代码后写了一个比较精简的Trajan_LAC算法。
;LL;const int MOD = 1e9 + 7;const int INF = 0x7fffffff;const int N = 1e5 + 10;map <string, int> ID;vector <int> G[N];vector <pair<int, int> > Query[N];string Name[N];int fa[N], ans[N];int findx(int x) {if(fa[x] == x) return x;else return fa[x] = findx(fa[x]);}void init(){ID.clear();memset(fa, -1, sizeof(fa));}void LCA(int u) {fa[u] = u;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];LCA(v);fa[v] = u;}for(int i = 0; i < Query[u].size(); i++) {pair <int, int> P = Query[u][i];if(fa[P.first] != -1) {ans[P.second] = findx(P.first);}}}int main() {#ifdef TYHfreopen(“in.txt”, “r”, stdin);#endif // TYHint n, m;scanf(“%d”, &n);string father, son;int tot = 1;init();for(int i = 0; i < n; i++) {cin >> father >> son;if(!ID[father]) ID[father] = tot, Name[tot++] = father;if(!ID[son]) ID[son] = tot, Name[tot++] = son;int x = ID[father], y = ID[son];G[x].push_back(y);}scanf(“%d”, &m);string n1, n2;for(int i = 0; i < m; i++) {cin >> n1 >> n2;int x = ID[n1], y = ID[n2];Query[x].push_back(make_pair(y, i));Query[y].push_back(make_pair(x, i));}LCA(1);for(int i = 0; i < m; i++) {cout << Name[ans[i]] << endl;}return 0;}
做对的事情比把事情做对重要。
