题面见校内OJ4695
题解：
首先利用斐波那契通项公式转化为等比数列求和。
然后树上差分，考虑修改对询问的贡献，发现有一部分与询问点的深度无关，另一部分有关，分开维护即可。
代码：
#include<bits/stdc++.h>#definelllonglong#definereregister#definegcget_char#definecsconstnamespaceIO{staticcsintRlen=1<<22|1;staticcharbuf[Rlen],*p1,*p2;inlinecharget_char(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}inlinecharpeek(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1;}inlinecharga(){while(!isalpha(peek()))++p1;returngc();}template<typenameT>inlineTget(){charc;Tnum;while(!isdigit(c=gc()));num=c^48;while(isdigit(c=gc()))num=((num+(num<<2))<<1)+(c^48);returnnum;}inlineintgi(){returnget<int>();}inlinellgL(){returnget<ll>();}}usingnamespaceIO;usingstd::cerr;usingstd::cout;csintmod=1e9+7;inlineintadd(inta,intb){a+=b-mod;returna+(a>>31&mod);}inlineintdec(inta,intb){a-=b;returna+(a>>31&mod);}inlineintmul(inta,intb){llr=(ll)a*b;returnr>=mod?r%mod:r;}inlineintpower(inta,intb,intres=1){for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));returnres;}inlinevoidInc(int&a,intb){a+=b-mod;a+=a>>31&mod;}inlinevoidDec(int&a,intb){a-=b;a+=a>>31&mod;}inlinevoidMul(int&a,intb){a=mul(a,b);}inlinevoidex_gcd(inta,intb,ll&x,ll&y){if(!b){x=1,y=0;return;}ex_gcd(b,a%b,y,x);y-=a/b*x;}inlineintinv(inta){if(!a)return1;llx,y;ex_gcd(a,mod,x,y);return(x%mod+mod)%mod;}csintinv2=(mod+1)>>1,inv5=inv(5);//考虑修改对询问的贡献，两个等差数列求和，分别为z^k/(1-z)和z^{d_y+1}\cdotz^k/(z^{d_x}(1-z))structcp{intx,y;//x+y\sqrt5cp(){}cp(int_x,int_y=0):x(_x),y(_y){}friendcpoperator+(cscp&a,cscp&b){returncp(add(a.x,b.x),add(a.y,b.y));}friendcpoperator-(cscp&a,cscp&b){returncp(dec(a.x,b.x),dec(a.y,b.y));}friendcpoperator*(cscp&a,cscp&b){returncp(add(mul(a.x,b.x),mul(5,mul(a.y,b.y))),add(mul(a.x,b.y),mul(a.y,b.x)));}friendcpoperator*(cscp&a,intb){returncp(mul(a.x,b),mul(a.y,b));}voidoperator+=(cscp&b){*this=*this+b;}voidoperator-=(cscp&b){*this=*this-b;}voidoperator*=(cscp&b){*this=*this*b;}voidoperator*=(intb){Mul(x,b),Mul(y,b);}};inlinecppower(cpa,llb){cpres(1,0);for(;b;b>>=1,a=a*a)if(b&1)res=res*a;returnres;}inlinecpinv(cpa){returncp(a.x,dec(0,a.y))*inv(dec(mul(a.x,a.x),mul(5,mul(a.y,a.y))));}cscpz=cp(1,1)*inv2,iz=inv(z),iz1=inv(cp(1)-z);csintN=1e5+7;intn,m;intlast[N],nxt[N],to[N],ecnt;inlinevoidadde(intu,intv){nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;}intfa[N],d[N],siz[N],son[N];inttop[N],in[N],out[N],clk;cpw[N],iw[N];voiddfs1(intu,intp){w[u]=w[p]*z;iw[u]=iw[p]*iz;d[u]=d[p]+1;in[u]=++clk;siz[u]=1;for(intree=last[u],v=to[e];e;v=to[e=nxt[e]]){dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}out[u]=clk;}voiddfs2(intu,inttp){top[u]=tp;for(intree=last[u],v=to[e];e;v=to[e=nxt[e]])dfs2(v,v==son[u]?tp:v);}inlineintLCA(intu,intv){while(top[u]!=top[v])d[top[u]]<d[top[v]]?v=fa[top[v]]:u=fa[top[u]];returnd[u]<d[v]?u:v;}cpt1[N],t2[N];inlinecpquery(cp*A,intp){cpres=cp(0);for(;p;p^=p&-p)res+=A[p];returnres;}inlinevoidupdate(cp*A,intp,cpad){for(;p<=clk;p+=p&-p)A[p]+=ad;}inlinevoidupdate(cp*A,intl,intr,cpad){update(A,l,ad);update(A,r+1,cp(0)-ad);}inlinecpquery(intu){if(!u)returncp(0);cpv1=query(t1,in[u]),v2=w[u]*z*query(t2,in[u]);returnv1-v2;}signedmain(){#ifdefzxyoifreopen("fibonacci.in","r",stdin);#else#ifndefONLINE_JUDGEfreopen("fibonacci.in","r",stdin);freopen("fibonacci.out","w",stdout);#endif#endifn=gi(),m=gi();for(intrei=2;i<=n;++i)adde(fa[i]=gi(),i);w[0]=iw[0]=cp(1);dfs1(1,0);dfs2(1,1);while(m--){switch(ga()){case'U':{intu=gi();llk=gL();cpt=power(z,k);update(t1,in[u],out[u],t*iz1);update(t2,in[u],out[u],t*iz1*iw[u]);break;}case'Q':{intu=gi(),v=gi(),p=LCA(u,v),pp=fa[p];cpk1=query(u),k2=query(v),k3=query(p),k4=query(pp),val=k1+k2-k3-k4;cout<<add(val.y,val.y)<<"\n";break;}}}return0;}
