HDOJ 4010 Query on The Trees LCT(二)
{ Splay(x); rt[ch[x][1]]=true; rt[ch[x][1]=y]=false; push_up(x); } return y; } bool judge(int u,int v) { while(pre[u]) u=pre[u]; while(pre[v]) v=pre[v]; return u==v; } void mroot(int r) { Access(r); Splay(r); update_rev(r); } void lca(int &u,int &v) { Access(v); v=0; while(u) { Splay(u); if(!pre[u]) return ; rt[ch[u][1]]=true; rt[ch[u][1]=v]=false; push_up(u); u=pre[v=u]; } } void link(int u,int v) { if(judge(u,v)) { puts("-1"); return ; } mroot(u); pre[u]=v; } void cut(int u,int v) { if(u==v||!judge(u,v)) { puts("-1"); return ; } mroot(u); Splay(v); pre[ch[v][0]]=pre[v]; pre[v]=0; rt[ch[v][0]]=true; ch[v][0]=0; push_up(v); } void Add(int u,int v,int w) { if(!judge(u,v)) { puts("-1"); return ; } lca(u,v); update_add(ch[u][1],w); update_add(v,w); key[u]+=w; push_up(u); } void query(int u,int v) { if(!judge(u,v)) { puts("-1"); return ; } lca(u,v); printf("%d\n",max(max(Max[v],Max[ch[u][1]]),key[u])); } struct Edge { int to,next; }edge[maxn*2]; int Adj[maxn],Size=0; void init() { memset(Adj,-1,sizeof(Adj)); Size=0; } void add_edge(int u,int v) { edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++; } void dfs(int u) { for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(pre[v]!=0) continue; pre[v]=u; dfs(v); } } int n; int main() { while(scanf("%d",&n)!=EOF) { init(); for(int i=0;i