pog loves szh III
Accepts: 63
Submissions: 483
Time Limit: 12000/6000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
pog在与szh玩游戏，首先pog在纸上画了一棵有根树，这里我们定义1为这棵树的根，然后szh在这棵树中选了若干个点，想让pog帮忙找找这些点的最近公共祖先在哪里，一个点为S的最近公共祖先当且仅当以该点为根的子树包含S中的所有点，且该点深度最大。然而，这个问题是十分困难的，出于szh对pog的爱，他决定只找编号连续的点，即。
输入描述
若干组数据(不超过)。每组数据第一行一个整数，表示树的节点个数。接下来，表示存在一条边连接这两个节点。接下来一行一个数组询问。接下来Q行每行两个数的点的最近公共祖先。
输出描述
对于每组的每个询问，输出一行，表示编号为li~ri的点的最近公共祖先的编号。
输入样例
51 21 33 44 551 22 33 43 51 5
输出样例
11331
Hint
珍爱生命，远离爆栈。
#include <iostream>#include <cstdio>#include <queue>#include <algorithm>#include <cstring>using namespace std;const int N = 400000 + 10;const int DEG = 20;int n, lca[N<<2];struct Edge{int to, next;}edge[N*2]; // Undirectional edgeint head[N], tot;void init(){tot = 0;memset(head, -1, sizeof(head));}void adde(int u, int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;}int fa[N][DEG], deg[N];void BFS(int root) //预处理得到之后二分搜索所需的顶点信息{queue<int> que;deg[root] = 0;fa[root][0] = root;que.push(root);while(!que.empty()){int u = que.front();que.pop();for(int i=1; i<DEG; i++)fa[u][i] = fa[fa[u][i-1]][i-1];for(int i=head[u]; i!=-1; i=edge[i].next){int v = edge[i].to;if(v == fa[u][0]) continue; //判断该节点之前是否访问过deg[v] = deg[u] + 1;fa[v][0] = u;que.push(v);}}cout<<endl;}int LCA(int u, int v)//二分搜索求出到达公共祖先所需的最少步数{if(deg[u] > deg[v]) swap(u, v);int hu = deg[u], hv = deg[v];int tu = u, tv = v;for(int det=hv-hu, i=0; det; det>>=1, i++)if(det&1) tv = fa[tv][i];if(tu == tv) return tu;for(int i=DEG-1; i>=0; i–)if(fa[tu][i] != fa[tv][i]){tu = fa[tu][i];tv = fa[tv][i];}return fa[tu][0];}#define root 1, n, 1#define lson L, mid, rt<<1#define rson mid+1, R, rt<<1|1#define lr rt<<1#define rr rt<<1|1void Up(int rt){lca[rt] = LCA(lca[lr], lca[rr]);}void bulid(int L, int R, int rt){if(L == R){lca[rt] = L;return ;}int mid = (L+R)>>1;bulid(lson);bulid(rson);Up(rt);}int Query(int l, int r, int L, int R, int rt)//求出区间[l, r]的LCA{if(l==L && r==R)return lca[rt];int mid = (L+R)>>1;if(r <= mid) return Query(l, r, lson);else if(l>mid) return Query(l, r, rson);else return LCA(Query(l, mid, lson), Query(mid+1, r, rson));}int main(){int n, q;while(~scanf("%d", &n)){init();int u, v;for(int i=0; i<n-1; i++){scanf("%d%d", &u, &v);adde(u, v);adde(v, u);}BFS(1);bulid(root);scanf("%d", &q);for(int i=0; i<q; i++){scanf("%d%d", &u, &v);printf("%d\n", Query(u, v, root));}}return 0;}
，停止每日在车水马龙的市井里忙碌的穿梭，
