QTREE系列1,4,5,6,7 LCT

admin 管理员组

文章数量: 887053

QTREE系列1,4,5,6,7 LCT

QTREE1

题意：

给出一棵N(N <= 10000)个点的树，要求支持：
1.改变第i条边的权值
2.求a->b上的最大边权

解：

直接树剖或LCT即可

代码

1.LCT(660ms)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#define L(i) (T[i].s[0])
#define R(i) (T[i].s[1])
#define F(i) (T[i].fa)
#define For(i,j,k) for(register int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(register int i=(j);i>=(int);i--)
#define Set(a,b) memset(a,b,sizeof(a))
#define Loc(i) (R(F(i))==i)
using namespace std;
const int N=20010;
inline void read(int &x){x=0;char c=getchar();int f=(c=='-');while(c<'0'||c>'9')c=getchar(),f!=(c=='-');while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
} 
int Begin[N],Next[N*2],to[N*2],e,n,m;
struct node{int s[2],fa,rev,v,mx;
};
struct LCT{node T[N];inline void clear(){Set(T,0);}inline bool isrt(int x){return R(F(x))!=x&&L(F(x))!=x;}inline void pushup(int x){T[x].mx=max(max(T[L(x)].mx,T[R(x)].mx),T[x].v);}inline void pushdown(int x){if(T[x].rev){T[x].rev=0,T[L(x)].rev^=1,T[R(x)].rev^=1;swap(L(x),R(x));}}inline void Pushdown(int x){if(!isrt(x))Pushdown(F(x));pushdown(x);}inline void Rotate(int x){int A=F(x),B=F(A),l=Loc(x),r=l^1,d=Loc(A);if(!isrt(A))T[B].s[d]=x;F(x)=B;F(A)=x,F(T[x].s[r])=A,T[A].s[l]=T[x].s[r],T[x].s[r]=A;pushup(A),pushup(x);}inline void splay(int x){Pushdown(x);while(!isrt(x)){if(!isrt(F(x)))Rotate(x);Rotate(x);}pushup(x);}inline void access(int x){for(int i=0;x;i=x,x=F(x))splay(x),R(x)=i,pushup(x);}inline void reverse(int x){access(x),splay(x),T[x].rev^=1;}inline int query(int x,int y){reverse(x),access(y),splay(y);return T[y].mx;}inline void modify(int x,int v){access(x),splay(x),T[x].v=v,pushup(x);}
}t;
char s[10];
void dfs(int u,int fa){for(int i=Begin[u];i;i=Next[i]){int v=to[i];if(v==fa)continue;t.T[v].fa=u;dfs(v,u);}
}
inline void add(int x,int y){to[++e]=y;Next[e]=Begin[x],Begin[x]=e;
}
int main(){int T;read(T);while(T--){t.clear();Set(Begin,0),e=0;read(n);For(i,1,n-1){int u,v,w;read(u),read(v),read(w);add(u,i+n),add(i+n,u),add(i+n,v),add(v,i+n);t.modify(i+n,w);}dfs(1,0);while(scanf("%s",s)!=EOF&&s[0]!='D'){int x,y;read(x),read(y);if(s[0]=='C')t.modify(x+n,y);else printf("%d\n",t.query(x,y));}}return 0;
}

树剖（200ms 用了zkw线段树，然后vjudge上就Rank1了）：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<ctime>
#include<queue>
#define For(i,j,k) for(register int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(register int i=(j);i>=(int)k;i--)
#define Rep(i,u) for(register int i=Begin[(u)],v=to[i];i;i=Next[i],v=to[i])
#define Set(a,b) memset((a),b,sizeof(a))
using namespace std;
const int N=10010,E=20010;
int Begin[N],Next[E],to[E],fa[N],siz[N],son[N],dep[N],w[N],e=1,top[N],cnt,n;
int d[N][3];
void read(int &x){x=0;char c=getchar();int f(0);while(c<'0'||c>'9'){c=getchar();if(c=='-')f=1;}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();if(f)x=-x;
}
inline void add(int x,int y){to[++e]=y,Next[e]=Begin[x],Begin[x]=e;}
struct zkwtree{int T[N<<2],M;inline void clear(){Set(T,0);}inline void pushup(int x){T[x]=max(T[x<<1],T[x<<1|1]);}void Build(){for(M=1;M<=n+1;M<<=1);}void add(int x,int v){for(T[x+=M]=v,x>>=1;x;x>>=1)pushup(x);}int query(int s,int t){int ret=-0x3f3f3f3f;for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){if(~s&1)ret=max(ret,T[s^1]);if(t&1)ret=max(ret,T[t^1]);}return ret;}
}t;
void dfs1(int u,int d){siz[u]=1;dep[u]=d;Rep(i,u)if(fa[u]!=v){fa[v]=u,dfs1(v,d+1),siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}
} 
void dfs2(int u,int tp){top[u]=tp,w[u]=++cnt;if(son[u])dfs2(son[u],top[u]);Rep(i,u)if(son[u]!=v&&fa[u]!=v)dfs2(v,v);
}
void init(){read(n);Set(son,0),Set(Begin,0),Set(fa,0),e=1,cnt=0;For(i,1,n-1){read(d[i][0]),read(d[i][1]),read(d[i][2]);add(d[i][0],d[i][1]),add(d[i][1],d[i][0]);}dfs1(1,1);dfs2(1,1);t.clear();t.Build();For(i,1,n-1){if(dep[d[i][0]]>dep[d[i][1]])swap(d[i][0],d[i][1]);t.add(w[d[i][1]],d[i][2]);}
}
int Max(int x,int y){int tmp=-0x3f3f3f3f;for(;top[x]!=top[y];){if(dep[top[x]]<dep[top[y]])swap(x,y);tmp=max(tmp,t.query(w[top[x]],w[x]));x=fa[top[x]];}if (x==y)return tmp;if (dep[x]>dep[y])swap(x,y);return max(tmp,t.query(w[x]+1,w[y]));
}
void solve(){char s[10];while(scanf("%s",s)!=EOF){int x,y;if (s[0]=='D')break;read(x),read(y);if (s[0]!='Q')t.add(w[d[x][1]],y);else printf("%d\n",Max(x,y));}
}
int main(){int _;for(read(_);_;_--){init();solve();}return 0;
} 

QTREE4

题意

给定一棵N(N <= 100000)个节点的树，边有权值，一开始每个节点全白，要求支持：
1.给某个节点反色（黑->白 白->黑）
2.查询最远两白点距离（特别的，只有一个白点答案为0）

题解

边权LCT维护子树信息，pushup时注意讨论。
对于一个节点维护这样几个值：
1.一个mutiset维护以该节点为根的子树中所有节点和它的最大，次大距离
2.一个mutiset维护以该节点为根的子树中最远两白点的路径长度
3.以该点为根的辅助树中离在对应的实际的树上最上面节点（其实就是辅助树上最左节点）最远白点距离
4..以该点为根的辅助树中离在对应的实际的树上最下面节点（其实就是辅助树上最右节点）最远白点距离
最后该节点为根的子树中的答案就可以通过上面的值合并出来
在每次反色时更新答案即可

代码

LCT（440ms）

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(int i=(j);i>=(int)k;i--)
#define Set(a,b) memset(a,b,sizeof(a))
#define Rep(i,u) for(int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])
#define L(i) (T[i].s[0])
#define R(i) (T[i].s[1])
#define F(i) (T[i].fa)
#define lmx(i) (T[i].lmx)
#define rmx(i) (T[i].rmx)
#define mx(i) (T[i].mx)
#define Loc(i) (R(F(i))==i)
#define S(i) (T[i].sum)
using namespace std;
const int N=200010 ,INF=0x3f3f3f3f;
inline void read(int &x){x=0;char c=getchar();int f(0);while(c<'0'||c>'9')f|=(c=='-'),c=getchar();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();if(f)x=-x;
}
int n,m,e,Begin[N>>1],Next[N],to[N],w[N],ans;
inline void add(int x,int y,int z){to[++e]=y,Next[e]=Begin[x],Begin[x]=e,w[e]=z;
}
inline int fir(multiset<int> &s){return s.size()?*s.rbegin():-INF;}
inline int sec(multiset<int> &s){return s.size()>1?*(++s.rbegin()):-INF;}
struct node{int s[2],lmx,rmx,mx,sum,len,w,fa; multiset<int>chain,path;
};
struct LCT{node T[N];inline void init(){For(i,0,n)lmx(i)=rmx(i)=mx(i)=-INF;}inline void pushup(int x){S(x)=S(L(x))+S(R(x))+T[x].len;int cha=max(T[x].w,fir(T[x].chain));int l=max(cha,rmx(L(x))+T[x].len);int r=max(cha,lmx(R(x)));lmx(x)=max(lmx(L(x)),S(L(x))+T[x].len+r);rmx(x)=max(rmx(R(x)),S(R(x))+l);mx(x)=max(mx(L(x)),mx(R(x)));mx(x)=max(mx(x),fir(T[x].chain)+sec(T[x].chain));mx(x)=max(mx(x),fir(T[x].path));mx(x)=max(mx(x),max(rmx(L(x))+T[x].len+r,lmx(R(x))+l));if(T[x].w==0)mx(x)=max(mx(x),max(fir(T[x].chain),0));}inline bool isrt(int x){return R(F(x))!=x&&L(F(x))!=x;}inline void Rotate(int x){int A=F(x),B=F(A),l=Loc(x),r=l^1,d=Loc(A);if(!isrt(A))T[B].s[d]=x;F(x)=B;F(A)=x,F(T[x].s[r])=A,T[A].s[l]=T[x].s[r],T[x].s[r]=A;pushup(A);}inline void splay(int x){while(!isrt(x)){int y=F(x);if(isrt(y))Rotate(x);else if(Loc(x)^Loc(y))Rotate(x),Rotate(x);else Rotate(y),Rotate(x);}pushup(x);}inline void access(int x){for(int i=0;x;i=x,x=F(x)){splay(x);if(R(x))T[x].chain.insert(lmx(R(x))),T[x].path.insert(mx(R(x)));if(i)T[x].chain.erase(T[x].chain.find(lmx(i))),T[x].path.erase(T[x].path.find(mx(i)));R(x)=i,pushup(x);}}inline void modify(int x){access(x);splay(x),T[x].w=(T[x].w==0)?-INF:0;pushup(x);ans=mx(x);}
}t;
void dfs(int u){Rep(i,u)if(t.T[u].fa!=v)t.T[v].fa=u,t.T[v].len=w[i],dfs(v),t.T[u].chain.insert(t.T[v].lmx),t.T[u].path.insert(t.T[v].mx);t.pushup(u);
}
char s[10];
int main(){read(n);t.init();For(i,1,n-1){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w),add(v,u,w);}   dfs(1);ans=t.T[1].mx;read(m);while(m--){int x;scanf("%s",s);if(s[0]=='A'){if(ans<0)puts("They have disappeared.");else printf("%d\n",ans);}else read(x),t.modify(x);}return 0;
}

QTREE5

Qtree4弱化版
给定一棵N(N <= 100000)个节点的树，边权为1，一开始每个节点全黑，要求支持：
1.给某个节点反色（黑->白 白->黑）
2.查询最远离v点最近白点距离（特别的，v是白点时答案为0）

题解

与QTREE4类似
最大值变最小值
答案不合并
边权是1

代码

LCT（450ms）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<map>
#define For(i,j,k) for(int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(int i=(j);i>=(int)k;i--)
#define Rep(i,u) for(int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])
#define L(i) (T[i].s[0])
#define R(i) (T[i].s[1])
#define F(i) (T[i].fa)
#define lmi(i) (T[i].lmi)
#define rmi(i) (T[i].rmi)
#define mi(i) (T[i].mi)
#define S(i) (T[i].sum)
#define Loc(i) (R(F(i))==i)
#define getchar getchar_unlocked//卡常数
using namespace std;
const int N=200010,INF=100000000;
inline int fir(multiset<int> &s){return s.size()>0?(*s.begin()):INF;}
inline void read(int &x){x=0;char c=getchar();int f(0);while(c<'0'||c>'9')f|=(c=='-'),c=getchar();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();if(f)x=-x;
}
int Begin[N],to[N],Next[N],e,n,m;
inline void add(int x,int y){to[++e]=y,Next[e]=Begin[x],Begin[x]=e;
}
struct node{int s[2],lmi,rmi,fa,sum,w,mi;multiset<int>chain;
};
struct LCT{node T[N];inline void init(){For(i,0,n)lmi(i)=T[i].w=rmi(i)=INF,T[i].chain.clear();}inline void pushup(int x){S(x)=S(L(x))+S(R(x))+1;int cha=min(T[x].w,fir(T[x].chain));int l=min(cha,rmi(L(x))+1),r=min(cha,lmi(R(x)));lmi(x)=min(lmi(L(x)),S(L(x))+1+r);rmi(x)=min(rmi(R(x)),S(R(x))+l);mi(x)=min(l,r);}inline bool isrt(int x){return R(F(x))!=x&&L(F(x))!=x;}inline void Rotate(int x){int A=F(x),B=F(A),l=Loc(x),r=l^1,d=Loc(A);if(!isrt(A))T[B].s[d]=x;F(x)=B;F(A)=x,F(T[x].s[r])=A,T[A].s[l]=T[x].s[r],T[x].s[r]=A;pushup(A);}inline void splay(int x){while(!isrt(x)){int y=F(x);//For(i,0,n)print(i);puts("");//printf("%d\n",isrt(y));if(isrt(y))Rotate(x);else if (Loc(y)^Loc(x))Rotate(x),Rotate(x);else Rotate(y),Rotate(x);}pushup(x);}inline void access(int x){for(int i=0;x;i=x,x=F(x)){splay(x);if(R(x))T[x].chain.insert(lmi(R(x)));if(i)T[x].chain.erase(T[x].chain.find(lmi(i)));R(x)=i,pushup(x);}}inline void modify(int x){access(x);splay(x);T[x].w=(T[x].w==0)?INF:0;pushup(x);}inline void query(int x){access(x);splay(x);printf("%d\n",mi(x)==INF?-1:mi(x));}
}t;
void dfs(int u){Rep(i,u)if(t.T[u].fa!=v){t.T[v].fa=u,dfs(v);t.T[u].chain.insert(t.T[v].lmi);}t.pushup(u);
}
int main(){int u,v;read(n);t.init();For(i,1,n-1){read(u),read(v);add(u,v),add(v,u);}dfs(1);read(m);while(m--){read(u),read(v);if(u==0)t.modify(v);        else t.query(v);}return 0;
}

QTREE6

题意

给定一棵N(N <= 100000)个节点的树，一开始每个节点全黑，要求支持：
1.反色
2.查询与之有联系的点的个数（两点有联系当且仅当两点路径上所有点颜色相同）

题解

维护两棵LCT，一棵黑树森林一棵白树森林
反色时在原来颜色的树中断开与父亲节点的连边，在更改后颜色树中连接与父亲节点的连边，然后查询就直接查询该点所在树大小即可，注意根节点的判断

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<set>
#define For(i,j,k) for(register int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(register int i=(j);i>=(int)k;i--)
#define Rep(i,u) for(register int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])
#define Set(a,b) memset(a,b,sizeof(a))
#define L(i) (T[i].s[0])
#define R(i) (T[i].s[1])
#define S(i) (T[i].sum)
#define ss(i) (T[i].ss)
#define F(i) (T[i].fa)
#define Loc(i) (R(F(i))==i)
#define getchar getchar_unlocked
using namespace std;
const int N=100001,INF=0x3f3f3f3f;
inline void read(int &x){x=0;char c=getchar();int f(0);while(c<'0'||c>'9')f|=(c=='-'),c=getchar();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();if(f)x=-x;
}
int Begin[N],Next[N<<1],to[N<<1],e,col[N],fa[N];
inline void add(int x,int y){to[++e]=y,Next[e]=Begin[x],Begin[x]=e;
}
struct node {int s[2],sum,fa,ss;
};
struct LCT{node T[N];inline void pushup(int x){S(x)=S(L(x))+S(R(x))+ss(x)+1;}inline bool isrt(int x){return R(F(x))!=x&&L(F(x))!=x;}inline void Rotate(int x){int A=F(x),B=F(A),l=Loc(x),r=l^1,d=Loc(A);if(!isrt(A))T[B].s[d]=x;F(x)=B;F(A)=x,F(T[x].s[r])=A,T[A].s[l]=T[x].s[r],T[x].s[r]=A;pushup(A);}inline void splay(int x){while(!isrt(x)){int y=F(x);if(!isrt(y))Rotate(x);Rotate(x);}pushup(x);}inline void access(int x){for(int i=0;x;i=x,x=F(x)){splay(x);if(R(x))ss(x)+=S(R(x));if(i)ss(x)-=S(i);R(x)=i;pushup(x);}   }inline void cut(int x){access(x),splay(x);F(L(x))=0,L(x)=0,pushup(x);}inline void link(int x,int y){access(y),splay(y);splay(x);F(x)=y,R(y)=x,pushup(y);}inline int findrt(int x){access(x),splay(x);while(L(x))x=L(x);return x;}inline void query(int x){int c=col[x];x=findrt(x);splay(x);printf("%d\n",col[x]==c?S(x):S(R(x)));}
}t[2];
void dfs(int u){Rep(i,u)if(fa[u]!=v){fa[v]=u,t[1].T[v].fa=u,dfs(v);t[1].T[u].ss+=t[1].T[v].sum;}t[1].pushup(u);
}
int n,m;
int main(){int tp,u;read(n);For(i,1,n-1){int u,v;read(u),read(v);add(u,v),add(v,u);col[i]=1;}col[n]=1;dfs(1);read(m);while(m--){read(tp),read(u);if(tp==0)t[col[u]].query(u);else{ if(fa[u])t[col[u]].cut(u),t[col[u]^1].link(u,fa[u]);col[u]^=1;}}return 0;
}

QTREE7

给定一棵N(N <= 100000)个节点的树，一开始每个节点全黑，要求支持：
1.反色
2.查询与之有联系的点中的最大权值（两点有联系当且仅当两点路径上所有点颜色相同）
3.修改u的点权

题解

与QTREE6类似
多加一个mutiset就好了

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<vector>
#define L(i) (T[i].s[0])
#define R(i) (T[i].s[1])
#define F(i) (T[i].fa)
#define Mx(i) (T[i].Mx)
#define W(i) (T[i].w)
#define Loc(i) (R(F(i))==i)
#define For(i,j,k) for(int i=(j);i<=(int)k;i++)
#define Forr(i,j,k) for(int i=(j);i>=(int)k;i--)
#define Set(a,b) memset(a,b,sizeof(a));
#define Rep(i,u) for(int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])
#define getchar getchar_unlocked
using namespace std;
const int N=100100,INF=0x3f3f3f3f;
inline int fir(multiset<int>&s){return s.size()?*s.rbegin():-INF;}
inline void read(int &x){x=0;char c=getchar();int f(0);while(c<'0'||c>'9')f|=(c=='-'),c=getchar();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();if(f)x=-x;
}
int Begin[N],to[N<<1],Next[N<<1],e,fa[N],col[N];
inline void add(int x,int y){to[++e]=y,Next[e]=Begin[x],Begin[x]=e;
}
struct node{int s[2],fa,w,Mx;multiset<int>mx;
};
struct LCT{node T[N];inline void pushup(int x){Mx(x)=max(W(x),fir(T[x].mx));if(L(x))Mx(x)=max(Mx(x),Mx(L(x)));if(R(x))Mx(x)=max(Mx(x),Mx(R(x)));}inline bool isrt(int x){return R(F(x))!=x&&L(F(x))!=x;}inline void Rotate(int x){int A=F(x),B=F(A),l=Loc(x),r=l^1,d=Loc(A);if(!isrt(A))T[B].s[d]=x;F(x)=B;F(A)=x,F(T[x].s[r])=A,T[A].s[l]=T[x].s[r],T[x].s[r]=A;pushup(A);}inline void splay(int x){while(!isrt(x)){if(!isrt(F(x)))Rotate(x);Rotate(x);}pushup(x);}inline void access(int x){for(int i=0;x;i=x,x=F(x)){splay(x);if(R(x))T[x].mx.insert(Mx(R(x)));if(i)T[x].mx.erase(T[x].mx.find(Mx(i)));R(x)=i,pushup(x);}}inline void link(int x,int y){access(y),splay(y),splay(x);F(x)=y,R(y)=x,pushup(y);}inline void cut(int x){access(x),splay(x),L(x)=F(L(x))=0,pushup(x);}inline int findrt(int x){access(x),splay(x);while(L(x))x=L(x);return x;}inline void query(int x){int c=col[x];x=findrt(x);splay(x);printf("%d\n",c==col[x]?Mx(x):Mx(R(x)));}inline void modify(int x,int val){access(x),splay(x);W(x)=val;pushup(x);}
}t[2];
int n,m;
void dfs(int u){Rep(i,u)if(fa[u]!=v){fa[v]=t[col[v]].T[v].fa=u,dfs(v);t[col[v]].T[u].mx.insert(t[col[v]].T[v].Mx);}t[0].pushup(u);t[1].pushup(u);
}
int main(){read(n);For(i,1,n-1){int u,v;read(u),read(v);add(u,v),add(v,u);}For(i,1,n)read(col[i]);For(i,1,n)read(t[0].T[i].w),t[1].T[i].w=t[0].T[i].w;dfs(1);read(m);while(m--){int tp,u,v;read(tp),read(u);if(tp==0)t[col[u]].query(u);else if(tp==1){if(fa[u])t[col[u]].cut(u),t[col[u]^1].link(u,fa[u]);col[u]^=1;}else {read(v);t[0].modify(u,v),t[1].modify(u,v);}}return 0;
}

注意不要换根，因为会改变树形态

本文标签： QTREE系列1 4 5 6 7 LCT