正解:树剖+线段树
解题报告:
看到$dep[lca]$啥的就想到之前托腮腮$CSP$模拟$D1T3$的那个套路,,,
然后试下这个想法,于是$dep[lca(x,y)]=sum_{i=1}^{infty}[ileq dep[lca(x,y)]]$,就可以是,从$x$到根全部加一然后查询$y$到根的权值和.
现在变成$sum_{i=l}^r dep[lca(i,x)]$,那就$l$到$r$到根全加一然后查询$x$到根的权值和.
显然考虑差分呗?就$1$到$r$全加一的权值和减去$1$到$l-1$全加一的权值和.
于是就从$1$枚举到$n$每次从当前节点到根全加一,顺便维护下这个答案就完事$QwQ$
#include<bits/stdc++.h> using namespace std; #define il inline #define lowbit(x) (x&(-x)) #define rg register #define gc getchar() #define ls(x) (x<<1) #define rs(x) ((x<<1)|1) #define ri register int #define rb register bool #define rc register char #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt) const int N=50000+5,mod=201314; int n,q,dfn[N],sz[N],top[N],fa[N],as[N],hs[N],dfn_cnt,tr[N<<2],ad[N<<2]; vector<int>son[N]; struct node{int id,x,op;}; vector<node>V[N]; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il void add(ri &x,ri y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;} il void dfs1(ri x) { sz[x]=1;ri siz=son[x].size(); rp(i,0,siz-1){dfs1(son[x][i]),sz[x]+=sz[son[x][i]];if(sz[son[x][i]]>sz[hs[x]])hs[x]=son[x][i];} } il void dfs2(ri x,ri tp) { top[x]=tp;dfn[x]=++dfn_cnt;if(hs[x])dfs2(hs[x],tp);ri siz=son[x].size(); rp(i,0,siz-1)if(son[x][i]^hs[x])dfs2(son[x][i],son[x][i]); } il void pushdown(ri x,ri l,ri r) { if(!ad[x])return; ri mid=(l+r)>>1; add(tr[ls(x)],1ll*ad[x]*(mid-l+1)%mod),add(tr[rs(x)],1ll*ad[x]*(r-mid)%mod); ad[ls(x)]+=ad[x],ad[rs(x)]+=ad[x];ad[x]=0; } void modify(ri x,ri l,ri r,ri to_l,ri to_r) { if(to_l<=l && r<=to_r){add(tr[x],r-l+1);add(ad[x],1);return;} pushdown(x,l,r); ri mid=(l+r)>>1;if(mid>=to_l)modify(ls(x),l,mid,to_l,to_r);if(mid<to_r)modify(rs(x),mid+1,r,to_l,to_r); tr[x]=(tr[ls(x)]+tr[rs(x)])%mod; } int query(ri x,ri l,ri r,ri to_l,ri to_r) { if(to_l<=l && r<=to_r)return tr[x]; pushdown(x,l,r);ri mid=(l+r)>>1,ret=0; if(mid>=to_l)ret=query(ls(x),l,mid,to_l,to_r);;if(mid<to_r)add(ret,query(rs(x),mid+1,r,to_l,to_r)); return ret; } int main() { freopen("4211.in","r",stdin);freopen("4211.out","w",stdout); n=read();q=read();rp(i,2,n)son[fa[i]=read()+1].push_back(i);dfs1(1);dfs2(1,1); rp(i,1,q){ri l=read(),r=read()+1,x=read()+1;V[l].push_back((node){i,x,-1});V[r].push_back((node){i,x,1});} rp(i,1,n) { ri nw=i;while(nw)modify(1,1,n,dfn[top[nw]],dfn[nw]),nw=fa[top[nw]]; for(auto j:V[i]) {nw=j.x;while(nw)add(as[j.id],j.op*query(1,1,n,dfn[top[nw]],dfn[nw])),nw=fa[top[nw]];} } rp(i,1,q)printf("%d ",as[i]); return 0; }