很有意思的题目，详细题解看这里 https://blog.csdn.net/qian99/article/details/38536559
自己的代码不知道哪里出了点问题
/*
rotate操作不会改变树的中序遍历结果，将初始的树按中序遍历结果拍扁在线段树上，
线段树结点维护每个结点的子树范围，自身权值和子树权值
*/
#pragma comment(linker,"/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 1000000007
#define ll long long
int ch[maxn][],pre[maxn],n,m;
int dfs_clock,lx[maxn],rx[maxn],w[maxn],id[maxn];//结点在线段树中的位置
ll val[maxn];
void dfs(int u){
if(ch[u][]) dfs(ch[u][]);//先遍历左子树
id[u]=++dfs_clock;val[dfs_clock]=w[u];//访问当前结点
if(ch[u][]){
lx[u]=lx[ch[u][]];//左边界
val[id[u]]+=val[id[ch[u][]]];
}
else lx[u]=id[u]; if(ch[u][]) dfs(ch[u][]);//在访问右子树
if(ch[u][]) {
rx[u]=rx[ch[u][]];//右边界
val[id[u]]+=val[id[ch[u][]]];
}
else rx[u]=id[u];
val[id[u]]%=mod;
}
inline void getinv(int x){
if(ch[x][]) lx[x]=lx[ch[x][]];
else lx[x]=id[x];
if(ch[x][]) rx[x]=rx[ch[x][]];
else rx[x]=id[x];
} //线段树部分
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
ll mul[maxn<<];
inline void pushup(int rt){
mul[rt]=mul[rt<<]*mul[rt<<|]%mod;
}
void build(int l,int r,int rt){
if(l==r){mul[rt]=val[l];return;}
int m=l+r>>;
build(lson);
build(rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){//查询区间[L,R]的乘积
if(L<=l && R>=r) return mul[rt];
int m=l+r>>;
ll res=;
if(L<=m) res=query(L,R,lson);
if(R>m) res*=query(L,R,rson),res%=mod;
return res;
}
void update(int pos,int l,int r,int rt,int val){
if(l==r){mul[rt]=val;return;}
int m=l+r>>;
if(pos<=m) update(pos,lson,val);
else update(pos,rson,val);
pushup(rt);
} void rotate(int x,int kind){//右转是0，左转是1,和伸展树操作刚好相反。。
int son=ch[x][kind];
if(son==) return;
ch[x][kind]=ch[son][kind^];
if(ch[son][kind^]) pre[ch[son][kind^]]=x;
if(pre[x]) ch[pre[x]][ch[pre[x]][]==x]=son;
pre[son]=pre[x];
ch[son][kind^]=x;
pre[x]=son; val[id[x]]=(w[x]+val[id[ch[x][]]]+val[id[ch[x][]]])%mod;
val[id[son]]=(w[son]+val[id[ch[son][]]]+val[id[ch[son][]]])%mod;
update(id[x],,n,,val[id[x]]);//修改线段树上的值
update(id[son],,n,,val[id[son]]);
getinv(x);getinv(son);
}
int main(){
int u,v,t,tcase=;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
memset(ch,,sizeof ch);
memset(pre,,sizeof pre);
w[]=val[]=dfs_clock=;
for(int i=;i<=n;i++){
scanf("%d%d%d",&w[i],&u,&v);
ch[i][]=u,ch[i][]=v;
if(u) pre[u]=i;
if(v) pre[u]=i;
}
for(int i=;i<=n;i++)if(pre[i]==) {dfs(i);break;}
build(,n,);
printf("Case #%d:\n",++tcase);
while(m--){
scanf("%d%d",&u,&v);
if(u==) printf("%lld\n",query(lx[v],rx[v],,n,));
else rotate(v,u);
}
}
}