自动搬运

查看原文

来自洛谷，原作者为

	紫钦 永远没有新的开始，因为我们从未停止。

搬运于2025-08-24 21:57:43，当前版本为作者最后更新于2018-02-20 22:28:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题统计l~r中所有点与z的lca的深度之和。

暴力就是把lca都求出来。。。

所以正解要么是一次求出多个lca，要么就是用玄学的方法把这个求多个deep的和转化一下。

前者我不会。

我们来看后者：

$deep[i]$是什么？——就是从 i 点到根有多少个点（包括 i ）。

我们从整体上考虑，发现对于一个询问：l , r , z 来说，所有的 lca 都在 z 到根的路径上。从而有一些点，它们对很多的 lca 的深度都有贡献，而这个贡献等于在这个点下面的 lca 的个数，所以我们可以把每个 lca 到根的路径上的每个点的权值都加一。然后从 z 向上走到根，沿路统计的权值就是答案了。

现在的问题就是：怎么找到这些 lca 并打上标记？

~~想想当初我们不会求 lca 的时候，~~要求lca（x , y）时，我们可以将根到 x 的所有点染色，然后从 y 向上爬，爬到的第一个有颜色的点就是lca (x , y)了，我们现在也可以这么做。

就是：对于一个询问： l , r , z ，我们把每个点 i （ l <= i <= r ） 到根的路径上的每一个点的权值都加一，记得上文我写到：所有的 lca 都在 z 到根的路径上，所以我们可以从 z 点向上爬到根，沿途统计的点权值之和，就是答案了。

这样就比暴力快不了多少了。

是时候考虑优化的问题了：我们每次的操作都是从某个点到根的，所以树链剖分+线段树就好了。

但是考虑到每次统计时，不能很好的排除 l ~ r 区间之外的点对 z->根 这条路径的贡献，所以我们每次都要清空线段树。

我们每次清空线段树，然后从 l ~ r 再添加一遍，树剖+线段树的复杂度就是$O(n * logn * logn)$的，还要做 q 次，复杂度依然不理想。

看数据范围，$O(n*logn*logn)$应该就是正解了，现在要想办法优化掉最后的那个 q 的复杂度。

我们看到区间 l~r ，~~总要想想差分的对不对，~~想到差分可以将询问拆开，而且每个拆开的区间之间是有重叠的，是可以转移的，而不用每次都清空。

而且差分后的数组只与右端点有关！

所以我们可以将差分后的区间按照右端点从小到大排序（左端点都是根），然后按从小到大的顺序添加点，每遇到一个询问就查询一次，从而排除掉区间之外的点的影响，也就优化掉一个 q 的复杂度。

至此，思路全部结束。

细节：

1.树剖+线段树的细节（这里不做赘述）。

2.差分当然要标记一下这个区间是 1 ~ l-1 还是 1~r 。

3.题目是以0为根，不习惯的朋友可以整体+1。整体+1也要注意，~~我做这题时就忘了询问也加一了，~~这也是个细节。

4.似乎没什么了。。。

AC代码（832ms）：

关键点的注释已经写到代码里了，若还有不懂的可以私聊我。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1 
using namespace std;

const int MAXN = 50005;
const int MOD = 201314;

struct Que {
	int ans1,ans2; // 询问的区间的答案是ans1-ans2。 
	Que() {ans1=ans2=0;}
}que[MAXN];
struct Que_part { //用来做差分的询问。 
	int num,pos,z; // 属于第几个询问； 询问是1~pos这个区间的和； 询问的点是z。 
	bool flag; // 类型：0：1~l-1 ； 1：1~r。
	Que_part() {num=pos=z=flag=0;} 
	Que_part(int a,int b,int c,bool d) {
		num=a; pos=b; z=c; flag=d;
	}
	
	inline bool operator < (const Que_part &a) const {
		return this->pos<a.pos;
	}
}que_p[MAXN<<1]; 

inline bool operator > (const Que_part &a,const Que_part &b) { // 我只是想看看operator定义到外面会怎么样。 
	return a.pos>b.pos;
}

int n,q; // 如题。 
int nex[MAXN],to[MAXN],en[MAXN]; // next; to; end; 变量名简陋，勿喷。 
int size[MAXN],fa[MAXN],dep[MAXN],son[MAXN]; // size; father; deep; heavy son(姑且这么叫吧);  
int top[MAXN],seq[MAXN],dfn[MAXN]; // seq是点到序列的映射，dfn是序列到点的映射。 
int sum[MAXN<<2],col[MAXN<<2],nowl,nowr; // 线段树；nowl,nowr表示当前查询/修改的区间的左右端点。 


void update(int rt)
{
	sum[rt]=(sum[rt<<1]+sum[rt<<1|1]) %MOD;
}
/*void build(int l,int r,int rt)
{
	if(l==r) {
		sum[rt]=col[rt]=0;
		return ;
	}
	col[rt]=0;
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	update(rt);
}*/
void color(int l,int r,int rt,int co)
{
	sum[rt]=(sum[rt]+(r-l+1)*co) %MOD;
	if(l<r) col[rt]=(col[rt]+co) %MOD;
}
void push_col(int l,int r,int rt)
{
	if(col[rt] && l<r) {
		int mid=(l+r)>>1;
		color(lson,col[rt]);
		color(rson,col[rt]);
	}
	col[rt]=0;
}
int query(int l,int r,int rt)
{
	if(nowl<=l && r<=nowr) return sum[rt];
	push_col(l,r,rt);
	int mid=(l+r)>>1,ans=0;
	if(nowl<=mid) ans+=query(lson);
	if(mid<nowr ) ans+=query(rson);
	return ans %MOD;
}
void modify(int l,int r,int rt)
{
	if(nowl<=l && r<=nowr) {
		color(l,r,rt,1);
		return ;
	}
	push_col(l,r,rt);
	int mid=(l+r)>>1;
	if(nowl<=mid) modify(lson);
	if(mid<nowr ) modify(rson);
	update(rt); 
}

void dfs1(int x)
{
	size[x]=1;
	for(int p=en[x];p;p=nex[p]) {
		if(to[p]!=fa[x]) { //其实用不着判断的，但我写习惯了。 
			dep[to[p]]=dep[x]+1;
			dfs1(to[p]);
			if(size[son[x]]<size[to[p]]) son[x]=to[p];
			size[x]+=size[to[p]];
		}
	}
}
void dfs2(int x,int anc)
{
	static int t=0;
	top[x]=anc;
	seq[x]=++t;
	dfn[t]=x;
	if(!son[x]) return ;
	dfs2(son[x],anc);
	for(int p=en[x];p;p=nex[p]) {
		if(to[p]!=fa[x] && to[p]!=son[x])
			dfs2(to[p],to[p]);
	}
}
int query_chain(int x,int y)
{
	int tx=top[x],ty=top[y],ans=0;
	while(tx!=ty) {
		if(dep[tx]<dep[ty]) {
			x^=y^=x^=y;
			tx^=ty^=tx^=ty;
		}
		nowl=seq[tx];nowr=seq[x];
		ans+=query(1,n,1);
		x=fa[tx];
		tx=top[x];
	}
	if(dep[x]>dep[y]) x^=y^=x^=y;
	nowl=seq[x];nowr=seq[y];
	ans+=query(1,n,1);
	return ans %MOD;
}
void modify_chain(int x,int y)
{
	int tx=top[x],ty=top[y];
	while(tx!=ty) {
		if(dep[tx]<dep[ty]) {
			x^=y^=x^=y;
			tx^=ty^=tx^=ty; 
		}
		nowl=seq[tx];nowr=seq[x];
		modify(1,n,1);
		x=fa[tx];
		tx=top[x];
	}
	if(dep[x]>dep[y]) x^=y^=x^=y;
	nowl=seq[x];nowr=seq[y];
	modify(1,n,1);
}

int main()
{
	int l,r,z,cnt=0,now=0; 
	scanf("%d %d",&n,&q);
	for(int i=2;i<=n;++i) { // 整体编号加一。 
		scanf("%d",&z);
		nex[++cnt]=en[fa[i]=++z];to[cnt]=i;en[z]=cnt; // 加一条 z->i 的有向边。
	}
	cnt=0; 
	for(int i=1;i<=q;++i) {
		scanf("%d %d %d",&l,&r,&z);
		++r;++z; 
		que_p[++cnt]=Que_part(i,l,z,0);
		que_p[++cnt]=Que_part(i,r,z,1);
	}
	
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	//build(1,n,1);// 我为什么要建树。。。 
	
	sort(que_p+1,que_p+cnt+1);
	
	for(int i=1;i<=cnt;++i) {
		while(now<que_p[i].pos) { // 一个点一个点往近添加。 now为当前添加过的点。 
			modify_chain(1,++now);
		}
		
		l=que_p[i].num; // 反正l没用了。就令l为当前子询问对应的母询问的序号吧。 
		if(que_p[i].flag) que[l].ans1=query_chain(1,que_p[i].z); // 也许不写这个1会让常数稍稍小一点。 
		else que[l].ans2=query_chain(1,que_p[i].z); 
	}
	
	for(int i=1;i<=q;++i) {
		printf("%d\n",(que[i].ans1-que[i].ans2+MOD) %MOD); // 记得要判负数。。。 
	}
	return 0;
}