提供一个异常好写的写法，只写了 2.81k，目前洛谷最短。

说句闲话其实是本题的正解应该是 $O(q\log n)$ 的，但是这题写什么乱七八糟的东西都能过。

大体思路应该是这个，不再复述。

但上面的构造方法需要较多空间，使用随机撒点的方法优化空间常数。

按编号大小从小到大加入关键点。用一个 bitset $vis$ 表示虚树边对应原树中的点。加入 $x$ 时枚举其祖先。如果存在祖先 $p$ 使得 $p$ 在虚树边上，那么该边在此处分叉。将 $p$ 加入虚树点集。

之后每次操作直接跳到祖先中第一个关键点。然后在虚树结构上跳即可。

实际上，可以撒 $\dfrac n K$ 个点，$K$ 为全局平衡二叉树的空间常数（应该要更大一些）。然后直接在虚树结构上跑这个东西。在优化空间常数的前提下，时间复杂度仍然为 $O(q\log n)$。

下面是关键，实现细节与坑点：

实际上，直接这样实现是很难写的。

对 $x\to y$ 的操作，差分成 $x\to 1,y\to 1,lca\to 1,f_{lca} \to 1$。

这个就很好写。考虑求 $lca$。

一种很古老的方法是，先将两个节点跳到同一深度，再一起往上跳。这里可以二分一起向上跳的距离。

那么要求 kth 祖先。这个就很好写了。

Q1：怎么求某个点所属的散块？

对于虚树上每条边 $x\to y$，在边上求出 $p$ 使得 $f_p=y$，建立映射 $p\to x$。直接把这个点向上跳到第一个关键点，记录从哪个儿子跳上来即可。

Q2：如果某个点不属于虚树边上，散块怎么处理？

跳到某个点 $x$ 满足这个点在虚树边上（$vis_x=1$），对于后面的散点，这些点就属于 $x$ 所属的散块了。

Q3：关键点数？

我也不知道，但是我知道我随机标记了 $4\times 10^3$ 个关键点，就是说可能有重复。

Q4：这鬼东西怎么跑过去的？？

$O(q\sqrt {n\log n})$ 加上巨大常数能过，我也很震撼。（而且几乎没有调关键点数）

虚树空间开两倍。倍两开间空树虚

#include<bits/stdc++.h>
#define Misaka namespace
#define Mikoto std
#define u unsigned
using Misaka Mikoto;
const int mxn=7e6+5;
const int BLOCK=4e3;
bitset<mxn> vis,que,vis2;
u a[mxn];
int f[mxn];
int n,cnt;
int t[BLOCK*2+5],dep[BLOCK*2+5],id[BLOCK*2+5];
u tag[BLOCK*2+5],sum[BLOCK*2+5];
unordered_map<int,int> mp,mp2;
u read()
{
	u s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s;
}
void add(int x)
{
	id[a[x]=++cnt]=x;
	for(;!vis[x];x=f[x]) vis[x]=1;
	if(!a[x]) id[a[x]=++cnt]=x;
}
struct pir
{
	int lst,top;
	u sum;
};
pir find(int x)
{
	int lst=x;
	u s=a[x];
	for(x=f[x];!vis[x];x=f[x]) s+=a[lst=x];
	return {lst,x,s};
}
void init(u A,u B,u C,u a0)
{
	int i,j;
	a[1]=id[1]=vis[1]=cnt=1,dep[0]=-1;
	for(i=0;i<BLOCK;i++)
		que[rand()%n+1]=1;
	for(i=2;i<=n;i++)
		if(que[i])
			add(i);
	vis2=vis,vis.reset();
	a[1]=0;
	for(i=2;i<=n;i++)
		a[i]=a[f[i]]+1;
	for(i=1;i<=cnt;i++)
		dep[i]=a[id[i]],vis[id[i]]=1,mp[id[i]]=i;
	a[0]=a0;
	for(i=1;i<=n;i++)
		a[i]=A*a[i-1]*a[i-1]+B*a[i-1]+C;
	sum[1]=a[1];
	for(i=2;i<=cnt;i++)
	{
		pir tp=find(id[i]);
		mp2[tp.lst]=i,sum[i]=tp.sum,t[i]=mp[tp.top];
	}
}
struct res
{
	int dep,bel;
};
res asktop(int x)
{
	if(x==1) return res({0,1});
	int lst=x,s=1;
	for(x=f[x];!vis[x];x=f[x]) lst=x,s++;
	return res({s+dep[mp[x]],mp2.find(lst)==mp2.end()?0:mp2[lst]});
}
int askkth(int x,int k)
{
	for(;k&&!vis[x];k--) x=f[x];
	if(!k) return x;
	for(x=mp[x];k>=dep[x]-dep[t[x]];x=t[x]) k-=dep[x]-dep[t[x]];
	for(x=id[x];k;k--) x=f[x];
	return x;
}
u ask(int x)
{
	if(!x) return 0;
	u s=0;
	int bel=0;
	for(;!vis[x];x=f[x]) 
	{
		if(!bel&&vis2[x]) bel=asktop(x).bel;
		s+=a[x]+tag[bel];
	}
	for(x=mp[x];x;x=t[x]) s+=sum[x];
	return s;
}
void add(int x,u v)
{
	if(!x) return;
	int bel=0;
	for(;!vis[x];x=f[x]) 
	{
		if(!bel&&vis2[x]) bel=asktop(x).bel;
		a[x]+=v,sum[bel]+=v;
	}
	for(x=mp[x];x;x=t[x]) 
		sum[x]+=(dep[x]-dep[t[x]])*v,tag[x]+=v;
}
int asklca(int x,int y)
{
	res bx=asktop(x),by=asktop(y);
	if(bx.dep<by.dep) swap(x,y),swap(bx,by);
	int cx=askkth(x,bx.dep-by.dep),i,dep=0;
	if(cx==y) return y;
	for(i=1<<22;i;i>>=1)
		dep+=i*(dep+i<=by.dep&&askkth(cx,dep+i)!=askkth(y,dep+i));
	return askkth(y,dep+1);
}
u ask(int x,int y)
{
	int lca=asklca(x,y);
	return ask(x)+ask(y)-ask(lca)-ask(f[lca]);
}
void add(int x,int y,u v)
{
	int lca=asklca(x,y);
	add(x,v),add(y,v),add(lca,-v),add(f[lca],-v);
}
int main()
{
	srand(time(0));
	read(),n=read();
	int i,j,q=read(),opt,x,y;
	u A=read(),B=read(),C=read(),a0=read(),last=0;
	for(i=2;i<=n;i++)
		f[i]=read();
	init(A,B,C,a0);
	while(q--)
	{
		last&=(1<<20)-1,opt=read(),x=read()^last,y=read()^last;
		if(opt) printf("%u\n",last=ask(x,y));
		else add(x,y,read()^last);
	}
}