看心情填坑

写完发现艹了标算。

英文题面先说题意，给一个树，每个节点有权值，初始为0，两个操作，一种是给定root和k，对于root子树中所有节点，将其权值加上Fib(D+k)，D是其到root的距离，第二种是链求和。

很显然2操作可以拆成4条到根的链之后直接爆，考虑每个1操作对其子树中答案的贡献，可以发现是$\sum_{i=k}^{deep[x]-deep[root]+k}Fib_{i}$的形式。

有$\sum_{i=1}^{n}Fib_{i}=Fib_{i+2}-1$所以那个东西等价于$Fib_{deep[x]-deep[root]+k+2}-Fib_{k+1}$

$Fib_{k+1}$是一个常量，直接维护就好，前面那个东西，可以拆成两个矩阵相乘来做，把$k-deep[root]+2$修改的时候做,$deep[x]$查询的时候再处理。

修改时矩阵先处理好，总复杂度$O(nlog)$

#include<cstdio>
#define mo 1000000007
using namespace std;
int n,m,cnt;
int head[100005];
char s[2];
int deep[100005],dfn[100005],ed[100005],fa[100005],size[100005],top[100005],son[100005];
inline long long lread(){
    long long ret=0;char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline int read(){
    int ret=0;char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
struct mar{
    int a[2][2];
    mar operator +(const mar &k)const{
        mar ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)ans.a[i][j]=(a[i][j]+k.a[i][j])%mo;
        return ans;
    }
    mar operator *(const mar &t)const{
        mar ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)ans.a[i][j]=0;
        for(int i=0;i<2;i++)
        	for(int j=0;j<2;j++)
        		for(int k=0;k<2;k++)ans.a[i][j]=(ans.a[i][j]+1LL*a[i][k]*t.a[k][j])%mo;
        return ans;
    }
    mar pow(long long k){
    	mar ans,tmp;
    	for(int i=0;i<2;i++)
    		for(int j=0;j<2;j++)tmp.a[i][j]=a[i][j];
    	ans.a[0][1]=ans.a[1][0]=0;ans.a[1][1]=ans.a[0][0]=1;
    	for(;k;k>>=1,tmp=tmp*tmp)if(k&1)ans=ans*tmp;
    	return ans;
    }
    void clear(){a[0][1]=a[0][0]=a[1][0]=a[1][1]=0;}
}f,nf;
struct tree{
	mar m;
	int y;
}t[400005];
struct edge{
	int to,next;
}e[200005];
void add(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
void dfs(int root){
	size[root]=1;
	for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa[root]){
		deep[e[i].to]=deep[root]+1;fa[e[i].to]=root;
		dfs(e[i].to);
		if(size[e[i].to]>size[son[root]])son[root]=e[i].to;
		size[root]+=size[e[i].to];
	}
}
void Dfs(int root){
	dfn[root]=++cnt;
	if(son[root]){top[son[root]]=top[root];Dfs(son[root]);}
	for(int i=head[root];i;i=e[i].next)if((son[root]!=e[i].to)&&(e[i].to!=fa[root]))top[e[i].to]=e[i].to,Dfs(e[i].to);
	ed[root]=cnt;
}
inline int lca(int u,int v){
	int U=top[u],V=top[v];
	while(U!=V){
		if(deep[U]<deep[V])v=fa[V],V=top[v];
		else u=fa[U],U=top[u];
	}
	return deep[u]>deep[v]?v:u;
}
#define lson index<<1
#define rson index<<1|1
#define mid ((l+r)>>1)
void pushdown(int index){
	t[lson].m=t[lson].m+t[index].m;
	t[rson].m=t[rson].m+t[index].m;
	t[lson].y=(t[lson].y+t[index].y)%mo;
	t[rson].y=(t[rson].y+t[index].y)%mo;
	t[index].m.clear();t[index].y=0;
}
inline tree query(int l,int r,int index,int k){
	if(l==r)return t[index];
	pushdown(index);
	if(k<=mid)return query(l,mid,lson,k);
	else return query(mid+1,r,rson,k);
}
void change(int l,int r,int index,int L,int R,mar M,int x){
	if((L<=l)&&(R>=r)){t[index].m=t[index].m+M,t[index].y=(t[index].y+x)%mo;return;}
	if(L<=mid)change(l,mid,lson,L,R,M,x);
	if(R>mid)change(mid+1,r,rson,L,R,M,x);
}
inline int Q(int k){
	tree tmp=query(1,n,1,dfn[k]);
	tmp.m=tmp.m*f.pow(deep[k]);
	int ans=tmp.m.a[1][0]-tmp.y;
	if(ans<0)ans+=mo;
	return ans;
}
int main(){
	n=read();m=read();
	f.a[0][1]=1;f.a[1][0]=1;f.a[1][1]=1;
	nf.a[0][0]=mo-1;nf.a[1][0]=1;nf.a[0][1]=1;
	for(int i=2;i<=n;i++){
		int u=read();
		add(u,i);add(i,u);
	}
	cnt=0;
	dfs(1);top[1]=1;Dfs(1);
	while(m--){
		scanf("%s",s);
		if(s[0]=='Q'){
			int x=read(),y=read(),l=lca(x,y),ans=0;
			ans=(Q(x)+Q(y)-Q(l))%mo;
			if(fa[l])ans=(ans-Q(fa[l]))%mo;
			if(ans<0)ans+=mo;
			printf("%d\n",ans);
		}else{
			int x=read();
			long long k=lread();int Tmp=f.pow(k+1).a[1][0];mar tmp;
			if(k-deep[x]+2<0)tmp=nf.pow(deep[x]-k-2);
			else tmp=f.pow(k-deep[x]+2);
			change(1,n,1,dfn[x],ed[x],tmp,Tmp);
		}
	}
}