BZOJ 3626 LNOI2014 LCA

[Description]

给出一个以0结点为根的n个结点的树，节点编号0~n-1。
设f(u)为结点u的深度，$lca(u,v)$为结点u,v的最近公共祖先。
给出q个询问(l,r,z)，要求每个询问输出: $\sum^r_{i=l}f(lca(i,z))$

[Hint]

$n,q≤5⋅10^4$

[Solution]

我们着重讨论思考过程。
纯暴力复杂度$O(q⋅n⋅log\ n)$，显然爆炸。
考虑模型转化。在计算某个询问的时候，我们可以将结点z到根路径上的所有点的点权设为1，答案即为结点[l,r]到根路径上的点权和，而这个操作又符合对称性和叠加性，即你可以将结点[l,r]到根路径上所有点的点权+1来计算z到根的路径上的点权和。所以想到了什么？树剖！
进一步思考，区间查询[l,r]并没有什么可循的规律，所以考虑是否可以查分查询。
当然是可以的，对于某个询问，我们先将1~l-1的点加进去，算出z的查询值，再将l~r的点加进去，再算出z的查询值减去之前的就是答案了。这个操作，对于所有询问都可以同时做，所以就可以离线处理了。
最后的复杂度为$O((q+n)⋅log\ n)$
每一步都精妙无比，好题~

[Code]

#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define pb push_back
#define ST SegmentTree
#define TCS TreeChainSubdivision
using namespace std;

typedef long long ll;

inline int read(){
  int x=0; char c=getchar();
  while(!isdigit(c)) c=getchar();
  while(isdigit(c)) x=x*10+c-'0',c=getchar();
  return x;
}

const int mod=201314;
const int maxn=5e4+1;
int res[maxn];
int L[maxn],R[maxn],Z[maxn]; 
vector<int> LL[maxn],RR[maxn];

int to[maxn],nxt[maxn],cur[maxn],fa[maxn],cnt;
void insert(int u,int v){
  to[cnt]=v,nxt[cnt]=cur[u],cur[u]=cnt++,fa[v]=u;
}

struct TCS{
  struct ST{
    static const int logn=17;
    int log,sum[1<<logn],flag[1<<logn];
    void init(int n){
      log=1; while(n) log<<=1,n>>=1;
    }
    void maintain(int l,int r,int o){
      int lc=o*2+1,rc=o*2+2;
      sum[o]=0;
      if(l<r) sum[o]=(sum[lc]+sum[rc])%mod;
      sum[o]=(sum[o]+(ll)(r-l+1)*flag[o])%mod;
    }
    void add(int l,int r,int L,int R,int o){
      if(l<=L && R<=r) flag[o]++;
      else{
        int M=(L+R)/2;
        if(l<=M) add(l,r,L,M,o*2+1);
        if(M<r) add(l,r,M+1,R,o*2+2);
      }
      maintain(L,R,o);
    }
    int query(int l,int r,int L,int R,int add,int o){
      if(l<=L && R<=r) return (sum[o]+(ll)(R-L+1)*add)%mod;
      else{
        int res=0,M=(L+R)/2;
        if(l<=M) res=(res+query(l,r,L,M,add+flag[o],o*2+1))%mod;
        if(M<r) res=(res+query(l,r,M+1,R,add+flag[o],o*2+2))%mod;
        return res;
      }
    }
  }st;
  
  int hson[maxn],d[maxn],size[maxn];
  void dfs1(int u,int dep){
    d[u]=dep,size[u]=1;
    for(int i=cur[u];i>=0;i=nxt[i]){
      int v=to[i];
      dfs1(v,dep+1);
      size[u]+=size[v];
      if(size[v]>size[hson[u]]) hson[u]=v;
    }
  }
  int top[maxn],id[maxn],cnt;
  void dfs2(int u,int tp){
    top[u]=tp,id[u]=++cnt;
    if(hson[u]) dfs2(hson[u],tp);
    for(int i=cur[u];i>=0;i=nxt[i]){
      int v=to[i];
      if(v!=hson[u]) dfs2(v,v);
    }
  }
  void init(int n){
    st.init(n);
    dfs1(1,1); dfs2(1,1);
  }
  
  void add(int u,int v){
    int tpu=top[u],tpv=top[v];
    while(tpu!=tpv){
        if(d[tpu]<d[tpv]){
        swap(u,v); swap(tpu,tpv);
      }
      st.add(id[tpu],id[u],1,st.log,0);
      u=fa[tpu],tpu=top[u];
    }
    if(u==v){ st.add(id[u],id[u],1,st.log,0); return; }
    if(d[u]<d[v]) swap(u,v);
    st.add(id[v],id[u],1,st.log,0);
  }
  int query(int u,int v){
    int res=0,tpu=top[u],tpv=top[v];
    while(tpu!=tpv){
      if(d[tpu]<d[tpv]){
        swap(u,v); swap(tpu,tpv);
      }
      res=(res+st.query(id[tpu],id[u],1,st.log,0,0))%mod;
      u=fa[tpu],tpu=top[u];
    }
    if(u==v) return res+st.query(id[u],id[u],1,st.log,0,0);
    if(d[u]<d[v]) swap(u,v);
    res=(res+st.query(id[v],id[u],1,st.log,0,0))%mod;
    return res;
  }
}tcs;

int main(){
  memset(cur,-1,sizeof(cur));
  int n=read(),m=read();
  for(int i=2;i<=n;i++) insert(read()+1,i);
  for(int i=0;i<m;i++){
    L[i]=read(),R[i]=read()+1,Z[i]=read()+1;
    LL[L[i]].pb(i),RR[R[i]].pb(i);
  }
  
  tcs.init(n);
  for(int i=1,sum=n<<1;i<=n && sum;i++){
    tcs.add(1,i);
    for(int j=0,lim=LL[i].size();j<lim;j++,sum--)
      res[LL[i][j]]=-tcs.query(1,Z[LL[i][j]]);
    for(int j=0,lim=RR[i].size();j<lim;j++,sum--)
      res[RR[i][j]]+=tcs.query(1,Z[RR[i][j]]);
  }
  
  for(int i=0;i<m;i++)
    printf("%d\n",(res[i]+mod)%mod);
    
  return 0;
}