做法颇多
算法一
形式化地描述要进行什么操作。
旋转节点：link/cut 。
更改两个点的子树和：单点修改。
询问一个点子树内子树和的积：子树询问。
可以在LCT上维护轻儿子信息（小Toptree），这样就可以子树询问
了。轻重边切换的时候顺便维护这个。
复杂度O(n log n)，期望得分70 - 100分。
算法二
子树询问的是积，具有可减性。
可以转化成link/cut，链乘除一个值，单点询问。
由于子树和可能为0，可以维护一个点上0的个数、非0值的积
用LCT维护。
复杂度O(n log n)，期望得分90 - 100分。
算法三
link/cut，单点修改，子树询问。
注意到虽然有link/cut，子树关系仍然是不变的。可以用Splay维
护dfs序。
复杂度O(n log n)，期望得分90 - 100分。
算法四
每次子树和只有2个点会修改。
问题在于dfs序会修改，导致子树信息比较麻烦。
注意到这是一棵平衡树，无论它怎么旋转，中序遍历是确定的。
而在中序遍历中，一个点的子树也是一个区间。
那么我们可以把中序遍历搞出来，然后维护每个点子树对应的区
间。
一次旋转操作只有2个点的子树区间会更改。可以根据左旋还是右
旋方便地讨论出来。
由于中序遍历序不变，只要用一个线段树维护就可以了。
然后就只剩下单点修改、区间求积了。
复杂度O(n log n)，期望得分100分。
hdu上线段树比较可靠
</pre><span style="font-family:Microsoft YaHei;font-size:14px;color:#000066;"></span><pre name="code" class="cpp"><span style="font-family:Microsoft YaHei;font-size:14px;color:#000066;">#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x)
{
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
const int N=200005;
const int P=1e9+7;
struct SEG{
int n,M,TH;
ll T[N<<2];
inline void Build(int n)
{
for (M=1,TH=0;M<n+2;M<<=1,TH++);
for (int i=1;i<(M<<1);i++)
T[i]=1;
}
inline void Change(int s,ll r){
T[s+=M]=r;
while (s>>=1)
T[s]=T[s<<1]*T[s<<1|1]%P;
}
inline ll Query(int s,int t)
{
ll ret=1;
for (s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1)
{
if (~s&1) ret=ret*T[s^1]%P;
if ( t&1) ret=ret*T[t^1]%P;
}
return ret;
}
}Seg;
int n,Q;
int val[N],lch[N],rch[N],fat[N];
ll sum[N];
inline void setch(int x,int y,int d){
if (d==0) lch[x]=y; else rch[x]=y;
fat[y]=x;
}
int pre[N],clk;
int st[N],ed[N];
inline void update(int x){
st[x]=ed[x]=pre[x];
if (lch[x]) st[x]=min(st[x],st[lch[x]]);
if (rch[x]) ed[x]=max(ed[x],ed[rch[x]]);
sum[x]=(sum[lch[x]]+sum[rch[x]]+val[x])%P;
Seg.Change(pre[x],sum[x]);
}
#define V G[p].v
inline void dfs(int u){
if (!u) return;
dfs(lch[u]);
st[u]=ed[u]=pre[u]=++clk;
dfs(rch[u]);
update(u);
}
int main(){
int order,iu,_t,T;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
read(T);
for (int _t=1;_t<=T;_t++)
{
printf("Case #%d:\n",_t);
read(n); read(Q);
for (int i=1;i<=n;i++)
{
read(val[i]); read(lch[i]); read(rch[i]); fat[lch[i]]=fat[rch[i]]=i;
sum[i]=val[i];
}
Seg.Build(n);
for (int i=n;i;i--)
if (fat[i])
(sum[fat[i]]+=sum[i])%=P;
clk=0; dfs(1);
while (Q--)
{
read(order); read(iu);
if (order==1){
int x=iu,y=rch[iu],f=fat[iu];
if (!y) continue;
int a=lch[x],b=lch[y],c=rch[y];
setch(x,a,0); setch(x,b,1);
setch(y,x,0); setch(y,c,1);
if (f) {if (lch[f]==x) setch(f,y,0); else setch(f,y,1); } else fat[y]=0;
update(x); update(y);
}else if (order==0){
int x=lch[iu],y=iu,f=fat[iu];
if (!x) continue;
ll a=lch[x],b=rch[x],c=rch[y];
setch(y,b,0); setch(y,c,1);
setch(x,a,0); setch(x,y,1);
if (f) {if (lch[f]==y) setch(f,x,0); else setch(f,x,1); } else fat[x]=0;
update(y); update(x);
}else{
printf("%lld\n",Seg.Query(st[iu],ed[iu]));
}
}
cl(fat);
}
return 0;
}</span>
模拟赛时打的splay
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x)
{
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
const ll P=1e9+7;
const int N=200005;
struct Splay{
#define oo 1<<30
struct node{
ll sum; ll mul; int size,idx;
node *p,*ch[2];
bool dir() { return p->ch[1]==this; }
void setc(node *x,int d) { ch[d]=x; x->p=this; }
void update(){
mul=ch[0]->mul*ch[1]->mul%P*sum%P;
size=ch[0]->size+ch[1]->size+1;
}
}*root,*null,Mem[N];
Splay() { root=null=Mem; null->ch[0]=null->ch[1]=null->p=null; null->mul=null->sum=1; null->size=0; }
inline void rot(node *x){
if (x==null) return;
if (x->p==root) root=x;
bool d=x->dir(); node *p=x->p;
if (p->p!=null) p->p->setc(x,p->dir()); else x->p=null;
p->setc(x->ch[d^1],d); x->setc(p,d^1); x->update(); p->update();
}
inline void splay(node *&rt,node *x){
if (x==null) return;
while (x!=rt)
if (x->p==rt)
rot(x);
else
x->dir()==x->p->dir()?(rot(x->p),rot(x)):(rot(x),rot(x));
rt=x; x->update();
}
inline void insert(node *z){
node *x=root,*y=null;
if (root==null) { root=z; return; }
while (x!=null)
y=x,x=x->ch[1];
y->setc(z,1);
splay(root,z);
}
inline void remove(node *x){
while (x->ch[0]!=null || x->ch[1]!=null)
x->ch[0]!=null?rot(x->ch[0]):rot(x->ch[1]);
x->p->ch[x->dir()]=null; x->p->update(); splay(root,x->p);
}
inline node* findkth(int k){
if (k>root->size) return null;
node *x=root;
while (k){
if (k==x->ch[0]->size+1) break;
k>x->ch[0]->size+1?k-=x->ch[0]->size+1,x=x->ch[1]:x=x->ch[0];
}
splay(root,x); return x;
}
inline int find(node *x){
splay(root,x);
return x->ch[0]->size+1;
}
}splay;
int n,Q;
int val[N],lch[N],rch[N],fat[N];
Splay::node *pos[N];
inline void setch(int x,int y,int d){
if (d==0) lch[x]=y; else rch[x]=y;
fat[y]=x;
}
int size[N];
ll sum[N];
#define V G[p].v
inline void dfs(int u,int fa){
splay.insert(pos[u]); size[u]=1;
if (lch[u])
dfs(lch[u],u),size[u]+=size[lch[u]];
if (rch[u])
dfs(rch[u],u),size[u]+=size[rch[u]];
}
inline void Init(){
for (int i=n;i;i--)
if (fat[i])
(sum[fat[i]]+=sum[i])%=P;
for (int i=1;i<=n+2;i++)
{
pos[i]=splay.Mem+i; pos[i]->size=1; pos[i]->idx=i;
pos[i]->sum=pos[i]->mul=sum[i];
pos[i]->ch[0]=pos[i]->ch[1]=pos[i]->p=splay.null;
}
splay.insert(pos[n+1]); dfs(1,0); splay.insert(pos[n+2]);
}
inline ll Sum(int l,int r){
Splay::node *x=splay.findkth(l-1+1),*y=splay.findkth(r+1+1);
splay.splay(splay.root,x);
splay.splay(x->ch[1],y);
return y->ch[0]->mul;
}
int main(){
int order,iu;
freopen("splay.in","r",stdin);
freopen("splay.out","w",stdout);
read(n); read(Q);
for (int i=1;i<=n;i++)
{
read(val[i]); read(lch[i]); read(rch[i]); fat[lch[i]]=fat[rch[i]]=i;
sum[i]=val[i];
}
Init();
while (Q--)
{
read(order); read(iu);
if (order==1){
int x=iu,y=rch[iu],f=fat[iu];
if (!y) continue;
int a=lch[x],b=lch[y],c=rch[y];
size[x]=size[a]+size[b]+1; size[y]=size[x]+size[c]+1;
sum[x]=(sum[a]+sum[b]+val[x])%P; sum[y]=(sum[x]+sum[c]+val[y])%P;
// lch[x]=a; rch[x]=b; lch[y]=x; rch[y]=c;
setch(x,a,0); setch(x,b,1);
setch(y,x,0); setch(y,c,1);
if (f) {if (lch[f]==x) setch(f,y,0); else setch(f,y,1); } else fat[y]=0;
splay.remove(pos[y]);
splay.splay(splay.root,pos[x]);
pos[x]->sum=sum[x];
pos[y]->setc(pos[x]->ch[0],0); pos[y]->setc(splay.null,1);
pos[y]->sum=sum[y];
pos[x]->setc(pos[y],0);
pos[y]->update(); pos[x]->update();
}else if (order==0){
int x=lch[iu],y=iu,f=fat[iu];
if (!x) continue;
ll a=lch[x],b=rch[x],c=rch[y];
Splay::node *alpha;
if (a)
{
int ran=splay.find(pos[a])-1;
ran+=size[a]-1;
alpha=splay.findkth(ran+1);
}
else
alpha=pos[x];
size[y]=size[b]+size[c]+1; size[x]=size[y]+size[a]+1;
sum[y]=(sum[b]+sum[c]+val[y])%P; sum[x]=(sum[y]+sum[a]+val[x])%P;
// lch[y]=b; rch[y]=c; lch[x]=a; rch[x]=y;
setch(y,b,0); setch(y,c,1);
setch(x,a,0); setch(x,y,1);
if (f) {if (lch[f]==y) setch(f,x,0); else setch(f,x,1); } else fat[x]=0;
splay.remove(pos[y]);
splay.splay(splay.root,pos[x]);
pos[x]->sum=sum[x]; pos[x]->update();
splay.splay(splay.root,alpha);
pos[y]->setc(alpha->ch[1],1); pos[y]->setc(splay.null,0);
pos[y]->sum=sum[y];
alpha->setc(pos[y],1);
pos[y]->update(); alpha->update();
}else{
int ran=splay.find(pos[iu])-1;
ll ret=Sum(ran,ran+size[iu]-1);
printf("%lld\n",ret);
}
}
return 0;
}
![UVALive 7141 BombX[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)