LCT

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
struct SPLAY { int fa,son[2],siz; bool rev; }t[N];
#define fa(p) t[p].fa
#define son(p) t[p].son
#define siz(p) t[p].siz
#define rev(p) t[p].rev
bool notroot (int p) { return son(fa(p))[0]==p||son(fa(p))[1]==p; }
//如果p和fa(p)连的是轻边,fa(p)就没有p这个儿子
//LCT的fa(p)记录原树上的父节点,son(p)则只有同一棵splay才有
//同一棵splay上的节点的中序遍历是按照原树上的深度递增的
void update (int p) { siz(p)=1+siz(son(p)[0])+siz(son(p)[1]); }
void pushrev (int p) { swap (son(p)[0],son(p)[1]); rev(p)^=1; }
void pushdown (int p)
{
    if (rev(p))
    {
        int ls=son(p)[0],rs=son(p)[1];
        if (ls) pushrev (ls);
        if (rs) pushrev (rs);
        rev(p)=0;
    }
}
int get (int p) { return son(fa(p))[1]==p; }
void rotate (int p)
{
    int f=fa(p),ff=fa(f),s=get (p);
    son(f)[s]=son(p)[s^1];
    if (son(f)[s]) fa(son(f)[s])=f;

    if (notroot (f)) son(ff)[son(ff)[1]==f]=p;
    fa(p)=ff;
    //由于使用了notroot，这两行要放在下面一行的上面

    son(p)[s^1]=f,fa(f)=p;
    update (f),update (p);
}
int st[N];
void splay (int p)
{
    int y=p; st[0]=0; st[++st[0]]=y;//!!!
    while (notroot (y)) st[++st[0]]=y=fa(y);//!!!
    while (st[0]) pushdown (st[st[0]--]);
    while (notroot (p))
    {
        int f=fa(p);
        if (notroot (f))
            rotate (get (f)==get (p)?f:p);
        rotate (p);
    }
}
void access (int p)
//把p到树根链接到同一条重链上,再让p成为重链的底端。
{
    for (int y=0; p; y=p,p=fa(p))
        splay (p),son(p)[1]=y,update (p);
}
void makeroot (int p)
//让p成为原树的根
{
    access (p),splay (p);
    pushrev (p);
}
int findroot (int p)
//找p所在原树的树根
{
    access (p),splay (p);
    while (son(p)[0]) pushdown (p),p=son(p)[0];
    splay (p);
    return p;
}
void split (int x,int y)
//把x-y拉出来变成1棵splay
//操作完后x为splay树根,所有对于这条链的操作/询问对x执行,如add/sum
{
    makeroot (y);
    access (x),splay (x);
}
bool link (int x,int y)
{
    makeroot (x);
    if (findroot (y)==x) return 0;
    fa(x)=y;
    return 1;
}
bool cut (int x,int y)
{
    makeroot (x);
    if (findroot (y)!=x||fa(y)!=x||son(y)[0]) return 0;
    //3种情况:
    //1.y不在x子树
    //2.x不是y的父节点
    //3.y有右儿子(原树上深度比y小,所以在x与y中间)
    fa(y)=son(x)[1]=0;
    update (x);
    return 1;
}
int a[N];
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    int n; sc(n);
    for (int i=1; i<=n; i++)
        sc(a[i]),link (i,min (n+1,i+a[i]));
    int m; sc(m);
    while (m--)
    {
        int op,x,k; sc(op),sc(x); ++x;
        if (op==1) split (x,n+1),pr(siz(x)-1);
        else
        {
            sc(k);
            cut (x,min (n+1,x+a[x]));
            a[x]=k,link (x,min (n+1,x+a[x]));
        }
    }
    return 0;
}

#include <bits/stdc++.h>
#define pr(p) printf("%lld\n",p)
const int oo=2139063143;
const int N=510000;
const int mod=51061;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
struct SPLAY { int fa,son[2]; LL add,mul,sum,w,siz; bool rev; }t[N];
#define fa(p) t[p].fa
#define son(p) t[p].son
#define add(p) t[p].add
#define mul(p) t[p].mul
#define rev(p) t[p].rev
#define sum(p) t[p].sum
#define siz(p) t[p].siz
#define w(p) t[p].w
bool notroot (int p) { return son(fa(p))[0]==p||son(fa(p))[1]==p; }
void update (int p)
{
	int ls=son(p)[0],rs=son(p)[1];
	sum(p)=(w(p)+sum(ls)+sum(rs))%mod;
	siz(p)=1+siz(ls)+siz(rs);
}
void pushrev (int p) { swap (son(p)[0],son(p)[1]); rev(p)^=1; }
void pushmul (int p,LL mul) { (w(p)*=mul)%=mod,(sum(p)*=mul)%=mod,(mul(p)*=mul)%=mod,(add(p)*=mul)%=mod; }
void pushadd (int p,LL add) { (w(p)+=add)%=mod,(sum(p)+=siz(p)*add%mod)%=mod,(add(p)+=add)%=mod; }
void pushdown (int p)
{
	int ls=son(p)[0],rs=son(p)[1];
	if (mul(p)!=1)
	{
		if (ls) pushmul (ls,mul(p));
		if (rs) pushmul (rs,mul(p));
		mul (p)=1;
	}
	if (add (p))
	{
		if (ls) pushadd (ls,add(p));
		if (rs) pushadd (rs,add(p));
		add (p)=0;
	}
	if (rev(p))
	{
		if (ls) pushrev (ls);
		if (rs) pushrev (rs);
		rev(p)=0;
	}
}
int get (int p) { return son(fa(p))[1]==p; }
void rotate (int p)
{
	int f=fa(p),ff=fa(f),s=get (p);
	son(f)[s]=son(p)[s^1];
	if (son(f)[s]) fa(son(f)[s])=f;
	if (notroot (f)) son(ff)[son(ff)[1]==f]=p;
	fa(p)=ff;
	son(p)[s^1]=f,fa(f)=p;
	update (f),update (p);
}
int st[N];
void splay (int p)
{
	int y=p; st[0]=0;
	st[++st[0]]=y;
	while (notroot (y)) st[++st[0]]=y=fa(y);
	while (st[0]) pushdown (st[st[0]--]);
	while (notroot (p))
	{
		int f=fa(p);
		if (notroot (f))
			rotate (get (f)==get (p)?f:p);
		rotate (p);
	}
}
void access (int p)
{
	for (int y=0; p; y=p,p=fa(p))
		splay (p),son(p)[1]=y,update (p);
}
void makeroot (int p)
{
	access (p),splay (p);
	pushrev (p);
}
int findroot (int p)
{
	access (p),splay (p);
	while (son(p)[0]) pushdown (p),p=son(p)[0];
	splay (p);
	return p;
}
void split (int x,int y)
{
	makeroot (y);
	access (x),splay (x);
}
bool link (int x,int y)
{
	makeroot (x);
	if (findroot (y)==x) return 0;
	fa(x)=y;
	return 1;
}
bool cut (int x,int y)
{
	makeroot (x);
	if (findroot (y)!=x||fa(y)!=x||son(y)[0]) return 0;
	fa(y)=son(x)[1]=0;
	update (x);
	return 1;
}
int main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	int n,q; sc(n),sc(q);
	for (int i=1; i<=n; i++)
		w(i)=sum(i)=siz(i)=mul(i)=1;
	for (int i=1; i< n; i++)
	{
		int u,v; sc(u),sc(v);
		link (u,v);
	}
	while (q--)
	{
		char sb[5]; scanf ("%s",sb+1);
		int u,v,c; sc(u),sc(v);
		if (sb[1]=='+') sc(c),split (u,v),pushadd (u,c);
		if (sb[1]=='-') cut (u,v),sc(u),sc(v),link (u,v);
		if (sb[1]=='*') sc(c),split (u,v),pushmul (u,c);
		if (sb[1]=='/') split (u,v),pr(sum(u)%mod);
	}
	return 0;
}