【BZOJ3626】LCA

    直接引用hzwer的题解吧。

    直接引用清华爷gconeice的题解吧

    显然，暴力求解的复杂度是无法承受的。
    考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现，实际上这个操作具有叠加性，且可逆。也就是说我们可以对于 l 到 r 之间的点 i，将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点（包括自身）的权值和就是这个询问的答案。把询问差分下，也就是用 [1, r] − [1, l − 1] 来计算答案，那么现在我们就有一个明显的解法。从 0 到 n − 1 依次插入点 i，即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和，显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n)，LCT的复杂度为 O((n + q)· log n)，均可以完成任务。至此，题目已经被我们完美解决。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500010,Mo=201314;

struct LCT
{
	struct Node
	{
		Node *c[2],*p,*lcp;
		int sum,size,v;
		int tag_inc;
		bool w() {return p->c[1]==this;}
	}*Null,*ID[maxn];

	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x)
	{
		if (x==Null) return;
		x->size=ls->size+rs->size+1;
		x->sum=ls->sum+rs->sum+x->v%Mo;
	}

	void Mark_Inc(Node *x,int o)
	{
		x->v=(x->v+o)%Mo;
		x->sum=(x->sum+(long long)x->size*o%Mo)%Mo;
		x->tag_inc=(x->tag_inc+o)%Mo;
	}

	void Push_Down(Node *x)
	{
		if (x==Null) return;
		if (x->tag_inc)
		{
			Mark_Inc(ls,x->tag_inc);
			Mark_Inc(rs,x->tag_inc);
			x->tag_inc=0;
		}
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		x->lcp=p->lcp;p->lcp=Null;
		Push_Down(p);Push_Down(x);
		x->c[!w]->p=p;p->p->c[p->w()]=x;
		x->p=p->p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x)
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=Null)
		{
			if (x->p->p==Null) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	void Access(Node *x)
	{
		Node *v=Null,*pre=x;
		while (x!=Null)
		{
			Splay(x);
			rs->lcp=x;
			rs->p=Null;
			rs=v;
			rs->p=x;
			rs->lcp=Null;
			Update(x);
			v=x;x=x->lcp;
		}
		Splay(pre);
	}

	void Link(Node *x,Node *v)
	{
		Access(x);
		x->lcp=v;
		Access(x);
	}

	void Init(int n)
	{
		for (int i=0;i<=n;i++) ID[i]=new Node;
		Null=ID[n];
		for (int i=0;i<=n;i++) ID[i]->size=1,ID[i]->lcp=ID[i]->c[0]=ID[i]->c[1]=ID[i]->p=Null,ID[i]->sum=ID[i]->v=ID[i]->tag_inc=0;
		Null->size=0;
	}

	void Link(int x,int y) {Link(ID[x],ID[y]);}
	void Add(int x) {Access(ID[x]);Mark_Inc(ID[x],1);}
	int Sum(int x) {Access(ID[x]);return ID[x]->sum;}
}T;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Query
{
	int x,z;
	int id;
	int f;
	bool operator< (const Query &b) const {return x<b.x;}
}Q[maxn<<1];

int n,q;
int ans[maxn];

int main()
{
	read(n);read(q);
	T.Init(n);
	for (int i=1,fa;i<n;i++) read(fa),T.Link(i,fa);
	for (int i=1,x,y,z;i<=q;i++) read(x),read(y),read(z),Q[(i<<1)-1].x=x-1,Q[(i<<1)-1].id=i,Q[(i<<1)-1].f=-1,Q[i<<1].x=y,Q[i<<1].id=i,Q[i<<1].f=1,Q[(i<<1)-1].z=Q[i<<1].z=z;
	sort(Q+1,Q+1+(q<<1));
	int qi=1;
	while (Q[qi].x==-1) qi++;
	for (int i=0;i<n;i++)
	{
		T.Add(i);
		while (Q[qi].x==i) ans[Q[qi].id]+=T.Sum(Q[qi].z)*Q[qi].f,qi++;
	}
	for (int i=1;i<=q;i++) printf("%d\n",(ans[i]%Mo+Mo)%Mo);
	return 0;
}