很有意思的题目，详细题解看这里 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][2],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][0]) dfs(ch[u][0]);//先遍历左子树 id[u]=++dfs_clock;val[dfs_clock]=w[u];//访问当前结点 if(ch[u][0]){ lx[u]=lx[ch[u][0]];//左边界 val[id[u]]+=val[id[ch[u][0]]]; } else lx[u]=id[u]; if(ch[u][1]) dfs(ch[u][1]);//在访问右子树 if(ch[u][1]) { rx[u]=rx[ch[u][1]];//右边界 val[id[u]]+=val[id[ch[u][1]]]; } else rx[u]=id[u]; val[id[u]]%=mod; } inline void getinv(int x){ if(ch[x][0]) lx[x]=lx[ch[x][0]]; else lx[x]=id[x]; if(ch[x][1]) rx[x]=rx[ch[x][1]]; else rx[x]=id[x]; } //线段树部分 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 ll mul[maxn<<2]; inline void pushup(int rt){ mul[rt]=mul[rt<<1]*mul[rt<<1|1]%mod; } void build(int l,int r,int rt){ if(l==r){mul[rt]=val[l];return;} int m=l+r>>1; 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>>1; ll res=1; 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>>1; 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==0) return; ch[x][kind]=ch[son][kind^1]; if(ch[son][kind^1]) pre[ch[son][kind^1]]=x; if(pre[x]) ch[pre[x]][ch[pre[x]][1]==x]=son; pre[son]=pre[x]; ch[son][kind^1]=x; pre[x]=son; val[id[x]]=(w[x]+val[id[ch[x][0]]]+val[id[ch[x][1]]])%mod; val[id[son]]=(w[son]+val[id[ch[son][0]]]+val[id[ch[son][1]]])%mod; update(id[x],1,n,1,val[id[x]]);//修改线段树上的值 update(id[son],1,n,1,val[id[son]]); getinv(x);getinv(son); } int main(){ int u,v,t,tcase=0; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); memset(ch,0,sizeof ch); memset(pre,0,sizeof pre); w[0]=val[0]=dfs_clock=0; for(int i=1;i<=n;i++){ scanf("%d%d%d",&w[i],&u,&v); ch[i][0]=u,ch[i][1]=v; if(u) pre[u]=i; if(v) pre[u]=i; } for(int i=1;i<=n;i++)if(pre[i]==0) {dfs(i);break;} build(1,n,1); printf("Case #%d: ",++tcase); while(m--){ scanf("%d%d",&u,&v); if(u==2) printf("%lld ",query(lx[v],rx[v],1,n,1)); else rotate(v,u); } } }