QTREE

树链剖分水题
[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;
}

就是把树拆成多条链。

路径上的修改和查找都是沿着链进行！
路径上的修改和查找都是沿着链进行！
路径上的修改和查找都是沿着链进行！