bzoj 2759一个动态树好题

真的是动态树好题,如果把每个点的父亲设成p[x],那么建出来图应该是一个环套树森林,拆掉一条边,就变成了动态树,考虑维护什么,对于LCT上每个节点,维护两组k和b,一组是他到他父亲的,一组是他LCT子树中深度最深的点到深度最浅的点的父亲的k和b,查询时只需查询一颗树中sf到自己的k和b,判断是否有唯一解,然后再解就可以了。注意不能换根,因为树的形态是固定的。

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 30005
#define mod 10007
using namespace std;
int n,p[N],q;
int qp(int a,int b){
int c=;
while(b){
if(b&)c=c*a%mod;
a=a*a%mod;b>>=;
}
return c;
}
struct Node{
Node *ch[],*fa,*sf;
int k,b,sumk,sumb,id;
Node();
void pushup();
void pushdown();
}*null=new Node,tree[N];
Node :: Node (){
ch[]=ch[]=fa=sf=null;
k=sumk=;b=sumb=id=;
}
void Node :: pushup(){
sumk=k;sumb=b;
sumb=(sumk*ch[]->sumb%mod+sumb)%mod;sumk=ch[]->sumk*sumk%mod;
sumb=(ch[]->sumk*sumb%mod+ch[]->sumb)%mod;sumk=sumk*ch[]->sumk%mod;
}
void rotate(Node *x){
Node *y=x->fa,*z=y->fa;
int w=y->ch[]==x;
x->ch[w]->fa=y;y->ch[w^]=x->ch[w];
y->fa=x;x->ch[w]=y;
if(z->ch[]==y)z->ch[]=x;
if(z->ch[]==y)z->ch[]=x;
x->fa=z;
y->pushup();x->pushup();
}
bool isroot(Node *x){
return x->fa->ch[]!=x && x->fa->ch[]!=x;
}
void splay(Node *x){
Node *y,*z;
while(!isroot(x)){
y=x->fa;z=y->fa;
if((z->ch[]==y&&y->ch[]==x)||(z->ch[]==y&&y->ch[]==x))
rotate(y);
rotate(x);
}
}
void access(Node *x){
Node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
x->pushup();
y=x;x=x->fa;
}
}
Node * find(Node *x){
access(x);splay(x);
while(x->ch[]!=null)x=x->ch[];
return x;
}
void cut(Node *x){
Node *rt=find(x);
if(rt==x)x->sf=null;
else{
access(x);
splay(x);
x->ch[]->fa=null;
x->ch[]=null;
x->pushup();
if(find(rt->sf)!=find(rt)){
rt->fa=rt->sf;
rt->sf=null;
}
}
}
void link(Node *x,Node *f,int k,int b){
x->k=k;x->b=b;
if(find(f)==find(x))x->sf=f;
else x->fa=f;
}
int query(Node *x){
Node *rt=find(x),*now=rt->sf;
access(now);splay(now);
if(now->sumk==){
if(now->sumb==)return -;
else return -;
}
int ans=(mod-now->sumb)*qp(((now->sumk-)+mod)%mod,mod-)%mod;
access(x);splay(x);
return (ans*x->sumk%mod+x->sumb)%mod;
}
int main(){
srand();
null->fa=null->ch[]=null->ch[]=null->sf=null;
scanf("%d",&n);
for(int i=,k,b;i<=n;i++){
tree[i].id=i;
scanf("%d%d%d",&k,&p[i],&b);
link(&tree[i],&tree[p[i]],k,b);
}
scanf("%d",&q);
char ch[];
int x,y,z,w;
while(q--){
scanf("%s",ch);
if(ch[]=='A'){
scanf("%d",&x);
printf("%d\n",query(&tree[x]));
}
else{
scanf("%d%d%d%d",&x,&y,&z,&w);
cut(&tree[x]);p[x]=z;
link(&tree[x],&tree[p[x]],y,w);
}
}
return ;
}
上一篇:【19道XSS题目】不服来战!


下一篇:BZOJ2759: 一个动态树好题