HDU 5052 LCT(二)
e Node *splay(){ go(); while(!isroot()){ if(!fa->isroot()) d()==fa->d()?fa->rot():rot(); rot(); } push_up(); return this; } inline Node *access(){ for(Node *p=this,*q=null;p!=null;q=p,p=p->fa){ p->splay()->setc(q,1); p->push_up(); } return splay(); } inline Node *find_root(){ Node *x; for(x=access();x->push_down(),x->ch[0]!=null;x=x->ch[0]); return x; } void make_root(){ access()->flip(); } }; Node pool[maxn],*tail; Node*node[maxn]; struct Edge{ int next,to; }edge[maxn*2]; int head[maxn],tol; inline void addedge(int u,int v){ edge[tol].to=v; edge[tol].next=head[u]; head[u]=tol++; } void dfs(int u,int pre){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre)continue; node[v]->fa=node[u]; dfs(v,u); } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n,m,T; scanf("%d",&T); while(T--){ scanf("%d",&n); tail=pool; null=tail++; null->val=null->
mm=null->rmm=0; null->Max=-INF;null->Min=INF; null->ch[0]=null->ch[1]=null->fa=null; null->add=null->rev=0; for(int i=1;i<=n;i++){ int w; scanf("%d",&w); node[i]=tail++; node[i]->clear(w); } memset(head,-1,sizeof(head));tol=0; for(int i=1;i
make_root(); node[v]->access(); printf("%d\n",node[v]->mm); node[v]->update_add(d); } } return 0; }