分析
考虑 $\sum\limits_{l\leq i\leq r}dep[LCA(i,z)]$ 怎么快速求。
对于每个 $i\in[l,r]$ ,把 $1$ 到 $i$ 路径上经过的所有点的权值 $+1$ 。那么 $1$ 到 $z$ 路径上所有点的权值和就是答案。
正确性可以画个图感性理解一下。
这样做的话,复杂度是 $O(Qn\log n)$ 。
考虑怎么优化掉那个 $Q$ 。
首先把所有询问差分,变为 $\sum\limits_{1\leq i\leq r}dep[LCA(i,z)]-\sum\limits_{1\leq i\leq l-1}dep[LCA(i,z)]$ ,也就是拆成两个询问。
那么把拆出来的 $2Q$ 个询问离线,按右端点排序后将每个点依次加入并顺便计算答案即可。
具体实现及细节见代码。
这题代码怎么比宝牌一大堆还短
代码
// =================================
// author: M_sea
// website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
const int mod=201314;
int n,Q;
struct Edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}
struct Query { int x,z,id,w; } q[N];
bool operator <(Query a,Query b) { return a.x<b.x; }
int tot=0;
int dep[N],fa[N],sz[N],hson[N],top[N],dfn[N],tim=0;
inline void dfs1(int u,int f) {
dep[u]=dep[f]+1,fa[u]=f,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
dfs1(v,u); sz[u]+=sz[v];
if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
}
}
inline void dfs2(int u,int anc) {
top[u]=anc,dfn[u]=++tim;
if (!hson[u]) return;
dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}
}
struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
int add[N<<2],sum[N<<2];
inline void pushup(int o) { sum[o]=(sum[ls]+sum[rs])%mod; }
inline void pushdown(int o,int l,int r) {
if (add[o]) {
int mid=(l+r)>>1;
add[ls]+=add[o],add[rs]+=add[o];
sum[ls]=(sum[ls]+(mid-l+1)*add[o])%mod;
sum[rs]=(sum[rs]+(r-mid)*add[o])%mod;
add[o]=0;
}
}
inline void update(int o,int l,int r,int ql,int qr,int w) {
if (ql<=l&&r<=qr) {
add[o]+=w,sum[o]=(sum[o]+w*(r-l+1))%mod;
return;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if (ql<=mid) update(ls,l,mid,ql,qr,w);
if (qr>mid) update(rs,mid+1,r,ql,qr,w);
pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return sum[o];
int mid=(l+r)>>1,res=0;
pushdown(o,l,r);
if (ql<=mid) res=(res+query(ls,l,mid,ql,qr))%mod;
if (qr>mid) res=(res+query(rs,mid+1,r,ql,qr))%mod;
pushup(o);
return res;
}
#undef ls
#undef rs
} T;
inline void modify(int u,int v) {
int tu=top[u],tv=top[v];
while (tu!=tv) {
if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
T.update(1,1,n,dfn[tu],dfn[u],1);
u=fa[tu],tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
T.update(1,1,n,dfn[v],dfn[u],1);
}
inline int query(int u,int v) {
int tu=top[u],tv=top[v],res=0;
while (tu!=tv) {
if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
res=(res+T.query(1,1,n,dfn[tu],dfn[u]))%mod;
u=fa[tu],tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
res=(res+T.query(1,1,n,dfn[v],dfn[u]))%mod;
return res;
}
int ans[N];
int main() {
n=read(),Q=read();
for (re int i=2;i<=n;++i) addEdge(read()+1,i);
dfs1(1,0); dfs2(1,1);
for (re int i=1;i<=Q;++i) {
int l=read()+1,r=read()+1,z=read()+1;
q[++tot]=(Query){l-1,z,i,-1};
q[++tot]=(Query){r,z,i,1};
}
sort(q+1,q+tot+1);
for (re int i=1,j=1;i<=tot;++i) {
if (!q[i].x) continue;
while (j<=q[i].x) modify(1,j),++j;
ans[q[i].id]=(ans[q[i].id]+q[i].w*query(1,q[i].z)+mod)%mod;
}
for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]%mod);
return 0;
}