动态树LCT

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=+,INF=-1u>>;
int v[maxn],maxv[maxn],minv[maxn],sumv[maxn],ch[maxn][],pre[maxn],top[maxn],flip[maxn],n,Q;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void maintain(int o){
int lc=ch[o][],rc=ch[o][];
maxv[o]=max(maxv[lc],maxv[rc]);
minv[o]=min(minv[lc],minv[rc]);
sumv[o]=sumv[lc]+sumv[rc];
if(v[o]){
sumv[o]+=v[o];
maxv[o]=max(maxv[o],v[o]);
minv[o]=min(minv[o],v[o]);
} return;
}
void pushdown(int o){
if(flip[o]){
flip[ch[o][]]^=;
flip[ch[o][]]^=;
swap(ch[o][],ch[o][]);
flip[o]=;
} return;
}
void rotate(int x,int d){
pushdown(x);
int y=pre[x],z=pre[y];
ch[y][d^]=ch[x][d];pre[ch[x][d]]=y;
ch[z][ch[z][]==y]=x;pre[x]=z;
ch[x][d]=y;pre[y]=x;
maintain(y);return;
}
void splay(int x){
int rt=x;
while(pre[rt]) rt=pre[rt];
if(x!=rt){
top[x]=top[rt];top[rt]=;
while(pre[x]){
pushdown(pre[x]);
rotate(x,ch[pre[x]][]==x);
} maintain(x);
} else pushdown(x);
return;
}
void access(int x){
int y=;
while(x){
splay(x);
top[ch[x][]]=x;pre[ch[x][]]=;
ch[x][]=y;
top[y]=;pre[y]=x;
maintain(x);
y=x;x=top[x];
} return;
}
void makeroot(int x){
access(x);splay(x);flip[x]^=;return;
}
void link(int u,int v){
makeroot(u);top[u]=v;return;
}
void query(int x,int y){
if(x==y){
puts("error");return;
}
makeroot(x);access(y);splay(y);
write(maxv[y]);putchar(' ');write(minv[y]);putchar(' ');write(sumv[y]);putchar('\n');
return;
}
void update(int pos,int cv){
splay(pos);v[pos]=cv;
maintain(pos);return;
}
void init(){
maxv[]=-INF;minv[]=INF;sumv[]=;
n=read();
for(int i=;i<n;i++){
int a=read(),b=read(),c=read();
v[i+n]=c;
link(a,i+n);link(i+n,b);
}
Q=read();
while(Q--)
{
int tp=read(),a=read(),b=read();
if(tp) query(a,b);
else update(a+n,b);
}
return ;
}
int main(){init();return ;}
上一篇:“equals”有值 与 “==”存在 “equals”只是比较值是否相同,值传递,==地址传递,null==a,避免引发空指针异常,STRING是一个对象==null,对象不存在,str.equals("")对象存在但是包含字符‘''


下一篇:Flask + Gunicorn + Nginx 部署