题意

　　给定一个有 $n$ 个节点，初始点权都为 $0$ 的无根树。

　　现在让你处理 $m$ 次操作，有下面 $4$ 种类型。

　　1.　　链上加斐波那契数列，其中 $f[1]=1,f[2]=1,f[3]=2,\cdots$

　　2.　　链上求和

　　3.　　给定树根，子树求和

　　4.　　回到第 $x$ 次询问时的状态。

　　强制在线。答案对于 $10^9+9$ 取模。

　　$n,m\leq 10^5$

题解

　　这大概又是一道我从去年留到今年的为数不多的坑。终于填掉了。

　　这次两个错误找了半天： 1. query 在子区间结果相加的时候忘记取模 2. 忘记考虑第三种操作中 $x=y$ 的情况。

　　下面讲算法。

　　首先我们来把斐波那契数列搞定。

　　矩阵乘法当然可以，但是麻烦、常数大。

　　首先我们找到斐波那契数列的通项公式：

$$f_i=\cfrac{\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\left(\cfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

　　我们可以暴力跑出来，在模 $10^9+9$ 意义下，有两个数满足 $ i^2\equiv 5 \pmod{10^9+9}$ 。

　　这里我们取 $\sqrt{5}\equiv 383008016 \pmod{10^9+9}$ 。

　　则：

　　$\cfrac{\sqrt{5}}{5}\equiv 276601605 \pmod{10^9+9}$

　　$\cfrac{1+\sqrt{5}}{2}\equiv 691504013 \pmod{10^9+9}$

　　$\cfrac{1-\sqrt{5}}{2}\equiv 308495997 \pmod{10^9+9}$

　　所以，

$$f_i\equiv 276601605\times(691504013^{\ n}-308495997^{\ n})\pmod{10^9+9}$$

　　于是我们成功把链上加斐波那契数列变成了链上加等比数列。

　　两个方向，两个公比，至少维护 $4$ 个量了。

　　树链修改，我们只需要树链剖分一下就可以了。

　　树链询问，通过树剖直接搞。

　　子树询问，由于我们要树剖，我们先会定根，但是这个询问的根是 $x$，子树是 $y$ ，不是我们定的，所以我们要分三种情况考虑一下。

　　1.　　$y=x$　　那么显然答案就是所有的 $n$ 个节点权值和。

　　2.　　$y\neq x$ 且 $y$ 是 $x$ 的祖先　　那么答案就是整棵树的权值和减去 $y$ 连向 $x$ 的那棵子树权值和。

　　3.　　$y\neq x$ 且 $y$ 不是 $x$ 的祖先　　那么答案显然就是 $y$ 这棵子树的答案

　　至于第四种操作，那么就是要你强行写可持久化，写主席树。

　　由于要写主席树，如果写下传的懒标记会很难写，所以我们采用标记永久化。

　　具体标记永久化方法看代码，这里不多加赘述。

　　代码很长，请慎重选择是否开做此题，谨防挖坑。

代码

#include 
     
      using namespace std;typedef long long LL;const int N=100005,S=N*200,mod=1e9+9;struct Gragh{	static const int M=N*2;	int cnt,y[M],nxt[M],fst[N];	void clear(){cnt=0;memset(fst,0,sizeof fst);}	void add(int a,int b){y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;}}g;int Pow(int x,int y){	int ans=1;	for (;y;y>>=1,x=1LL*x*x%mod)		if (y&1)			ans=1LL*ans*x%mod;	return 0;}int n,m,V=276601605,V1=691504013,V2=308495997;int Pow1[N],Pow2[N],Sum1[N],Sum2[N];int size[N],depth[N],son[N],fa[N][20],in[N],out[N],top[N],p[N],ap[N],Time=0,cnp=0;void Get_Gen_Info(int x,int pre,int d){	size[x]=1,son[x]=-1,depth[x]=d,fa[x][0]=pre;	for (int i=1;i<20;i++)		fa[x][i]=fa[fa[x][i-1]][i-1];	for (int i=g.fst[x];i;i=g.nxt[i])		if (g.y[i]!=pre){			int y=g.y[i];			Get_Gen_Info(y,x,d+1);			size[x]+=size[y];			if (son[x]==-1||size[y]>size[son[x]])				son[x]=y;		}}void Get_Top(int x,int Top){	in[x]=++Time,ap[p[x]=++cnp]=x,top[x]=Top;	if (son[x]!=-1)		Get_Top(son[x],Top);	for (int i=g.fst[x];i;i=g.nxt[i]){		int y=g.y[i];		if (y!=son[x]&&y!=fa[x][0])			Get_Top(y,y);	}	out[x]=Time;}struct Seg{	int sum,L1,L2,R1,R2,ls,rs,len;	int TagV(){return (1LL*(L1+R1)*Sum1[len-1]-1LL*(L2+R2)*Sum2[len-1]+sum)%mod;}}T[S];int root[N],tot=0;int build(int L,int R){	int rt=++tot;	T[rt].len=R-L+1;	if (L==R)		return rt;	int mid=(L+R)>>1;	T[rt].ls=build(L,mid);	T[rt].rs=build(mid+1,R);	return rt;}void update(int prt,int &rt,int L,int R,int xL,int xR,int type,int Lv,int Rv){	if (rt==0)		rt=prt;	if (L>xR||R
      
       >1,lenL=mid-L+1,lenR=R-mid;	update(T[prt].ls,T[rt].ls,L,mid,xL,xR,type,Lv,Rv+lenR);	update(T[prt].rs,T[rt].rs,mid+1,R,xL,xR,type,Lv+lenL,Rv);	T[rt].sum=(T[T[rt].ls].TagV()+T[T[rt].rs].TagV())%mod;}int query(int rt,int L,int R,int xL,int xR,int L1,int L2,int R1,int R2){	if (L>xR||R
       
        >1,lenL=mid-L+1,lenR=R-mid;	return (query(T[rt].ls,L,mid,xL,xR,L1,L2,1LL*R1*Pow1[lenR]%mod,1LL*R2*Pow2[lenR]%mod)	    +query(T[rt].rs,mid+1,R,xL,xR,1LL*L1*Pow1[lenL]%mod,1LL*L2*Pow2[lenL]%mod,R1,R2))%mod;}int LCA(int x,int y){	if (depth[x]
        
         =0;i--)		if (depth[x]-(1<
         
          =depth[y])			x=fa[x][i];	if (x==y)		return x;	for (int i=19;i>=0;i--)		if (fa[x][i]!=fa[y][i])			x=fa[x][i],y=fa[y][i];	return fa[x][0];}void Tupdate(int prt,int &rt,int x,int y){	int Fx=top[x],Fy=top[y],Tx=0,Ty=0;	int lca=LCA(x,y),len=depth[x]+depth[y]-depth[lca]*2+1;	while (Fx!=Fy)		if (depth[Fx]>depth[Fy]){			update(prt,rt,1,n,p[Fx],p[x],1,0,Tx+1-(n-p[x]));			Tx+=depth[x]-depth[Fx]+1;			x=fa[Fx][0],Fx=top[x];		}		else {			Ty+=depth[y]-depth[Fy]+1;			update(prt,rt,1,n,p[Fy],p[y],0,len-Ty+1-(p[Fy]-1),0);			y=fa[Fy][0],Fy=top[y];		}	if (depth[x]
          
           depth[y]) swap(x,y); ans=(ans+query(rt,1,n,p[x],p[y],0,0,0,0))%mod; return ans;}int main(){ scanf("%d%d",&n,&m); Pow1[0]=Pow2[0]=1,Sum1[0]=Sum2[0]=1; for (int i=1;i<=n;i++){ Pow1[i]=1LL*Pow1[i-1]*V1%mod,Sum1[i]=(Sum1[i-1]+Pow1[i])%mod; Pow2[i]=1LL*Pow2[i-1]*V2%mod,Sum2[i]=(Sum2[i-1]+Pow2[i])%mod; } g.clear(); for (int i=1,a,b;i
           
            =0;j--) if (depth[x]-(1<
            
             depth[y]) x=fa[x][j]; LASTANS=query(root[i],1,n,1,n,0,0,0,0)-query(root[i],1,n,in[x],out[x],0,0,0,0); LASTANS=(1LL*LASTANS*V%mod+mod)%mod; printf("%d\n",LASTANS); } else { LASTANS=query(root[i],1,n,in[y],out[y],0,0,0,0); LASTANS=(1LL*LASTANS*V%mod+mod)%mod; printf("%d\n",LASTANS); } } if (opt[1]=='Q'&&opt[2]=='C'){ scanf("%d",&y); LASTANS=Tquery(root[i],x,y); LASTANS=(1LL*LASTANS*V%mod+mod)%mod; printf("%d\n",LASTANS); } } return 0;}