1 条题解
-
0
题解
易知 一定在根节点到 的路径上,而它的深度等价于它到根节点路径上的结点个数。
只需将结点 到根结点的路径上的结点都 ,然后结点 到根结点的路径上数值总和就是最近公共祖先的深度。
这样,我们就只需要将 这些点到根结点的路径上结点全部 ,再统计 到根结点路径上结点的数值总和即可。
考虑优化。首先有个显然的优化, 的问题可以转化为 和 的问题。此时问题转化为求若干个左端点为 的问题。
不妨将这些问题的右端点排序,依次将 到根结点路径上的点 ,若遇到询问就查询答案即可。
时间复杂度 。
// 2023.07.26 #include<bits/stdc++.h> using namespace std; const int mod=201314; int n,m,fa[50001],ans[50001]; struct Edge{ int to,nxt; }edge[50001]; int cntEdge,head[50001]; void addEdge(int u,int v){ edge[++cntEdge]={v,head[u]},head[u]=cntEdge; } int siz[50001],dep[50001],heavy[50001]; void init(int id){ siz[id]=1; for(int i=head[id];i;i=edge[i].nxt){ dep[edge[i].to]=dep[id]+1; init(edge[i].to); if(siz[edge[i].to]>siz[heavy[id]]) heavy[id]=edge[i].to; siz[id]+=siz[edge[i].to]; } } int cntdfn,dfn[50001],rnk[50001]; int top[50001]; void decomposition(int id,int x){ // x 为当前链顶端 top[id]=x,dfn[++cntdfn]=id,rnk[id]=cntdfn; if(!heavy[id])return; decomposition(heavy[id],x); for(int i=head[id];i;i=edge[i].nxt) if(edge[i].to!=heavy[id]) decomposition(edge[i].to,edge[i].to); } namespace SegmentTree{ int sum[200001],lazy[200001],len[200001]; void pushdown(int id){ if(lazy[id]){ sum[id<<1]+=len[id<<1]*lazy[id]; lazy[id<<1]+=lazy[id]; sum[(id<<1)+1]+=len[(id<<1)+1]*lazy[id]; lazy[(id<<1)+1]+=lazy[id]; sum[id<<1]%=mod,sum[(id<<1)+1]%=mod; lazy[id]=0; } } void pushup(int id){ sum[id]=(sum[id<<1]+sum[(id<<1)+1])%mod; } void build(int id,int l,int r){ sum[id]=lazy[id]=0; len[id]=r-l+1; if(l<r){ int mid=l+r>>1; build(id<<1,l,mid); build((id<<1)+1,mid+1,r); } } void updateAddOne(int id,int l,int r,int x,int y){ if(x<=l&&r<=y){ lazy[id]++; sum[id]+=len[id]; sum[id]%=mod; return; } int mid=l+r>>1; pushdown(id); if(x<=mid)updateAddOne(id<<1,l,mid,x,y); if(mid<y)updateAddOne((id<<1)+1,mid+1,r,x,y); pushup(id); } void updateList(int x,int y){ // 将从 x 到 y 这条链加 1 int topx=top[x],topy=top[y]; while(topx!=topy){ if(dep[topx]<dep[topy]) swap(x,y),swap(topx,topy); updateAddOne(1,1,n,rnk[topx],rnk[x]); x=fa[topx],topx=top[x]; } if(dep[x]>dep[y])swap(x,y); updateAddOne(1,1,n,rnk[x],rnk[y]); } int querySum(int id,int l,int r,int x,int y){ if(x<=l&&r<=y)return sum[id]; int mid=l+r>>1,res=0; pushdown(id); if(x<=mid)res+=querySum(id<<1,l,mid,x,y); if(mid<y)res+=querySum((id<<1)+1,mid+1,r,x,y); return res%mod; } int queryList(int x,int y){ // 查询从 x 到 y 这条链的总和 int res=0,topx=top[x],topy=top[y]; while(topx!=topy){ if(dep[topx]<dep[topy]) swap(x,y),swap(topx,topy); res+=querySum(1,1,n,rnk[topx],rnk[x]); x=fa[topx],topx=top[x]; } if(dep[x]>dep[y])swap(x,y); res+=querySum(1,1,n,rnk[x],rnk[y]); return res%mod; } } struct Query{ int id,weight; int pos,x; // pos 表示询问 [1,pos] 区间,x 为结点 z bool operator<(Query tmp)const{ return pos<tmp.pos; } }Q[100001]; int cntQuery; int main(){ scanf("%d%d",&n,&m); for(int i=2;i<=n;i++){ scanf("%d",fa+i),fa[i]++; addEdge(fa[i],i); } for(int i=1;i<=m;i++){ int l,r,z; scanf("%d%d%d",&l,&r,&z); l++,r++,z++; Q[++cntQuery]={i,-1,l-1,z}; Q[++cntQuery]={i,1,r,z}; } sort(Q+1,Q+1+cntQuery); dep[1]=1; init(1); SegmentTree::build(1,1,n); decomposition(1,1); int nowpos=0; for(int i=1;i<=cntQuery;i++){ while(nowpos<Q[i].pos) SegmentTree::updateList(1,++nowpos); ans[Q[i].id]+=Q[i].weight*SegmentTree::queryList(1,Q[i].x); } for(int i=1;i<=m;i++) printf("%d\n",(ans[i]%mod+mod)%mod); return 0; }
- 1
信息
- ID
- 3626
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 44
- 已通过
- 18
- 上传者