调了半天才调出来的东西啊……233，在写tarjan的循环时写错了，把_v_ask写成了_v，太容易写错了，一定要多加注意，这个模版还需要练习，线段树也是。。
Tarjan::
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include<bits/stdc++.h> #define MAXN 1000005 #define MAXM 1000005 #define EdgeLoop(e,node) for(int e=_first[node];e!=-1;e=_next[e]) #define EdgeAskLoop(e,node) for(int e=_first_ask[node];e!=-1;e=_next_ask[e]) int n, m, s; int _father[MAXN]; int graph_m_ptr = 0, graph_m_ptr_ask = 0; int _u[MAXN], _v[MAXN], _next[MAXN], _first[MAXN]; bool _visited[MAXN]; int _u_ask[MAXN], _v_ask[MAXN], _next_ask[MAXN], _first_ask[MAXN]; int _ans[MAXM]; int _find(int x){ if (_father[x] == x)return x; return _father[x] = _find(_father[x]); } void _merge(int x, int y){//merge y branch to x branch _father[_find(x)] = _find(y); } void insert_edge(int s, int t){ _u[graph_m_ptr] = s; _v[graph_m_ptr] = t; _next[graph_m_ptr] = _first[s]; _first[s] = graph_m_ptr; graph_m_ptr++; } void insert_edge_ask(int s, int t){ _u_ask[graph_m_ptr_ask] = s; _v_ask[graph_m_ptr_ask] = t; _next_ask[graph_m_ptr_ask] = _first_ask[s]; _first_ask[s] = graph_m_ptr_ask; graph_m_ptr_ask++; } void tarjan(int u){ _visited[u] = true; EdgeLoop(e, u){ if (!_visited[_v[e]]){ tarjan(_v[e]); _merge(_v[e],u); } } EdgeAskLoop(e, u){ if (_visited[_v_ask[e]]){ _ans[e/2] = _find(_v_ask[e]); } } } using namespace std; int main(){ ios::sync_with_stdio(false); cin >> n >> m >> s; for (int i = 1; i <= n; i++){ _father[i] = i; } memset(_first, -1, sizeof(_first)); memset(_first_ask, -1, sizeof(_first_ask)); for (int i = 1; i <= n - 1; i++){ int x, y; cin >> x >> y; insert_edge(x, y); insert_edge(y, x); } for (int i = 1; i <= m; i++){ int a, b; cin >> a >> b; insert_edge_ask(a, b); insert_edge_ask(b, a); } tarjan(s); for (int i = 0; i < m; i++){ cout << _ans[i] << endl; } } |
树上倍增：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include<bits/stdc++.h> using namespace std; int edge_ptr = 0; struct edge{ int v; int next; }edges[1000005]; int head[500005]; int n, m, s; int father[500005][25],depth[500005]; bool visited[500005]; inline void insert_edge(int s,int t){ edge_ptr++; edges[edge_ptr].v = t; edges[edge_ptr].next = head[s]; head[s] = edge_ptr; } inline void dfs(int u){ visited[u] = true; for (int i = 1, len = 1; len <= depth[u]; i++, len <<= 1){ father[u][i] = father[father[u][i - 1]][i - 1]; } for (int e = head[u]; e != -1;e=edges[e].next){ if (!visited[edges[e].v]){ depth[edges[e].v] = depth[u] + 1; father[edges[e].v][0] = u; dfs(edges[e].v); } } } inline int query(int x, int y){ if (depth[x] > depth[y])swap(x,y); int diff = depth[y] - depth[x]; for (int i = 0, two = 1; diff != 0; two <<= 1, i++){ if (diff&two){ y = father[y][i]; diff -= two; } } if (x == y)return x; for (int i = log2(depth[x]); i >= 0; i--){ if (father[x][i] != father[y][i]){ x = father[x][i]; y = father[y][i]; } } return father[x][0]; } int main(){ ios::sync_with_stdio(false); memset(head, -1, sizeof(head)); cin >> n >> m >> s; for (int i = 1; i <= n - 1; i++){ int x, y; cin >> x >> y; insert_edge(x, y); insert_edge(y, x); } dfs(s); for (int i = 1; i <= m; i++){ int x, y; cin >> x >> y; cout << query(x, y) << endl; } } |