树链剖分水题
[https://www.bilibili.com/video/av4482146/]
DFS1
int dep[MaxN],fa[MaxN],son[MaxN],sz[MaxN];
void bfs1(int u,int pre,int d){
dep[u] = d;
fa[u] = pre;
son[u] = -1;
sz[u] = 1;
for(int i = 0;i < G[u].size();++i){
int &v = G[u][i];
if(v == pre) continue;
dfs1(v,u,d+1);
if(son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
}
}
DFS2
int id[MaxN],top[MaxN];
int tot;
void dfs2(int u,int sp){
id[u] = ++tot;
top[u] = sp;
if(son[u] == -1) return;
dfs2(son[u],sp);
int gusz = G[u].size();
for(int i = 0;i < gusz;++i){
int &v = G[u][i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v,v);
}
}
Find
int Find(int u,int v){
int f1 = top[u],f2 = top[v];
int tmp;
while(f1 != f2){
if(dep[f1] < dep[f2]){
swap(f1,f2);swap(u,v);
}
tmp = max(tmp,query(1,id[f1],id[u]));
u = fa[f1]; f1 = top[u];
}
if(u == v) return tmp;
if(dep[u] > dep[v]) swap(u,v);
tmp = max(tmp,query(1,id[son[u]],id[v]));
return tmp;
}
就是把树拆成多条链。
路径上的修改和查找都是沿着链进行！
路径上的修改和查找都是沿着链进行！
路径上的修改和查找都是沿着链进行！
