树链剖分LCA
主要在于,首先要找x的k级祖先,从这个点出发不断往上找他的顶端端点,如果顶端端点所在的深度小于k级祖先所在的深度(也就是dep[x] – k),继续找他的父亲节点所在链的顶端端点,循环比较顶端端点和k级祖先所在深度,当x的顶端端点的深度大于k级祖先所在的深度时,说明所要找的祖先在这条链上,此时我们可以求得此时x节点的深度与k级祖先深度的差值,最后结果就是x节点的dfs序-差值得到k祖先的dfs序,再转换成原先序列所对应的点。
代码:
1 #include2 #include 96 sum[rt] += (C * (r - l + 1)); 97 lazy[rt] += C; 98 return; 99 } 100 int m = (l + r) >> 1; 101 PushDown(rt, m - l + 1, r - m); 102 if (m >= L) Update(L, R, C, l, m, rt << 1); 103 if (m < R) Update(L, R, C, m + 1, r, rt << 1 | 1); 104 PushUp(rt); 105 } 106 int Query(int L, int R, int l, int r, int rt) { 107 if (l >= L && r R) { 108 return sum[rt]; 109 } 110 int m = (l + r) >> 1; 111 PushDown(rt, m - l + 1, r - m); 112 int ans = 0; 113 if (m >= L) ans = (ans + Query(L, R, l, m, rt << 1)); 114 if (m < R) ans = (ans + Query(L, R, m + 1, r, rt << 1 | 1)); 115 return ans; 116 } 117 }st; 118 119 int rt = 1; 120 121 inline int Jump(int x, int k) { 122 int d = dep[x] - k; 123 if (d 0) return 1; 124 //else if (d < 0) return 1; 125 while (dep[top[x]] > d) x = fa[top[x]]; 126 d = dep[x] - d; // 求当前x节点与k级祖先的深度差 127 return rnk[dfn[x] - d]; 128 } 129 130 int jump(int x, int k) { 131 while (k >= dfn[x] - dfn[top[x]] + 1 && x != rt) { 132 k -= (dfn[x] - dfn[top[x]] + 1); 133 x = fa[top[x]]; 134 } 135 return rnk[dfn[x] - k]; 136 } 137 138 int main() { 139 140 ios::sync_with_stdio(false); 141 cin.tie(0), cout.tie(0); 142 cin >> n >> q >> s; 143 memset(head, -1, sizeof(head)); 144 tot = 0; 145 for (int i = 1; i ) { 146 int x; 147 cin >> x; 148 if (!x) rt = i; 149 else add(x, i); 150 } 151 dep[rt] = 1; 152 dfs1(rt); 153 dfs2(rt, rt); 154 st.Build(1, cnt, 1); 155 int lastans = 0; 156 ll ans = 0; 157 for (int i = 1; i ) { 158 int x = (get(s) ^ lastans) % n + 1; 159 int k = (get(s) ^ lastans) % dep[x]; 160 lastans = Jump(x, k); 161 ans ^= 1ll * i * lastans; 162 } 163 cout << ans << "\n"; 164 165 return 0; 166 }3 #include 4 #include 5 #include
Original: https://www.cnblogs.com/wabi/p/16557209.html
Author: Kyrizer_W
Title: P5903 【模板】树上 k 级祖先
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/587862/
转载文章受原作者版权保护。转载请注明原作者出处!