树链剖分

P4315

线段树+树链剖分模板题。

注意要将边转化到点上。

• 还有要注意dfs序不能在dfs1中求，不然的话dfs需的顺序就不是先重儿子再轻儿子了。

  void dfs1(int u,int f){
      sz[u]=1;
      for(int i=head[u];~i;i=e[i].nxt){
          int v=e[i].v,w=e[i].w;
          if(v==f)continue;
          dep[v]=dep[u]+1;
          fa[v]=u;
          p[v]=w;
          dfs1(v,u);
          sz[u]+=sz[v];
          if(sz[son[u]]<sz[v])son[u]=v;
      }
      return;
  }
  void dfs2(int u,int t){
      id[u]=++tot; 
      top[u]=t;
      a[tot]=p[u];
      if(son[u])dfs2(son[u],t);
      for(int i=head[u];~i;i=e[i].nxt){
          int v=e[i].v;
          if(v==fa[u] || v==son[u])continue;
          dfs2(v,v);
      }
      return;
  }
  

• 结论:

• \(树链剖分时dfs序一定要在dfs2中求；\)

• \(当线段树同时涉及op1:"将[l,r]加k"和op2:"将[l,r]改为k"时，要注意维护的顺序，先op2再op1,并且lazytag要分别维护。\)