題意
題目連結
Sol
長鍊剖分
又是一個用各種花式技巧優化的暴力
它的主要思想是:對于每個節點,把深度最深的子節點當做重兒子,它們之間的邊當做重邊
這樣就會有一些非常好的輕質
- 所有鍊長總和是\(O(n)\)級别的
- 任意一個點的\(k\)級祖先的子樹深度\(\geqslant k\)
首先我們維護出每一個重鍊頭向上\(len[i]\)個節點是什麼,沿着重鍊走向下\(len[i]\)個節點是什麼
\(len[i]\)表示該節點所在重鍊的長度
同時預處理出找祖先的倍增數組
每次詢問的時候,首先找到\(k\)的第一個二進制位(假設為\(r\)),利用倍增數組向上跳\(2^r\)次,然後結合之前處理好的重鍊頭對應的數組特判一下即可
時間複雜度:
預處理倍增數組複雜度為\(O(nlogn)\)
預處理每個數的第一個二進制位複雜度為\(O(n)\)
每次詢問複雜度為\(O(1)\)
總複雜度為\(O(nlogn + m)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, md[MAXN], dep[MAXN], fa[MAXN][21], son[MAXN], top[MAXN], len[MAXN], B[MAXN];
vector<int> v[MAXN], U[MAXN], D[MAXN];//up and down
void dfs(int x, int _fa) {
md[x] = dep[x] = dep[_fa] + 1; fa[x][0] = _fa;
for(int i = 1; i < 20; i++)
if(fa[x][i - 1]) fa[x][i] = fa[fa[x][i - 1]][i - 1];
else break;
for(int i = 0, to; i < v[x].size(); i++) {
if((to = v[x][i]) == _fa) continue;
dfs(to, x);
if(md[to] > md[son[x]]) son[x] = to, md[x] = md[to];
}
}
void dfs2(int x, int topf) {
top[x] = topf; len[x] = md[x] - dep[topf] + 1;
if(!son[x]) return ;
dfs2(son[x], topf);
for(int i = 0, to; i < v[x].size(); i++)
if(!top[(to = v[x][i])]) dfs2(to, to);
}
void Pre() {
int now = 0;
for(int i = 1; i <= N; i++) {
if(!(i & (1 << now))) now++;
B[i] = now;
}
for(int i = 1; i <= N; i++) {
if(i == top[i]) {
for(int j = 1, x = i; j <= len[i] && x; j++) x = fa[x][0], U[i].push_back(x);
for(int j = 1, x = i; j <= len[i] && x; j++) x = son[x], D[i].push_back(x);
}
}
}
int Query(int x, int k) {
if(k > dep[x]) return 0;
if(k == 0) return x;
x = fa[x][B[k]]; k ^= 1 << B[k];
if(!k) return x;
if(dep[x] - dep[top[x]] == k) return top[x];
if(dep[x] - dep[top[x]] < k) return U[top[x]][k - dep[x] + dep[top[x]] - 1];
else return D[top[x]][dep[x] - dep[top[x]] - k - 1];
}
int main() {
N = read();
for(int i = 1; i <= N - 1; i++) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
dfs(1, 0); dfs2(1, 1);
Pre();
int lastans = 0, Q = read();
while(Q--) {
int x = read() ^ lastans, y = read() ^ lastans;
printf("%d\n", lastans = Query(x, y));
}
return 0;
}
作者:自為風月馬前卒
個人部落格http://attack204.com//
出處:http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有,歡迎轉載,但未經作者同意必須保留此段聲明,且在文章頁面明顯位置給出原文連接配接,否則保留追究法律責任的權利。