首页 > 代码库 > BZOJ 3319 黑白树 并查集+线段树
BZOJ 3319 黑白树 并查集+线段树
这这这这这这什么毒瘤题！！！！！！！！！！！！！！！！！！！！！！！！！！！！
卡LCT（优秀的LCT由于是均摊本身就带着2,3的常数在，而且这道题对于LCT标记十分难维护，又得乘上4,5然后就炸了），卡树剖，卡正解，但是暴力能A！！！！！！！！！！！！！！！！！！！！！！
所谓正解就是线段树为护dfs序+并查集删点去重，这东西在每个点一秒的时候都过不了Po姐都虚。
但是我在网上看到一个大佬有一个神思路A掉了
下面是我改过之后的的TLE程序
#include<cstdio> #include<cstring> #include<ctime> #include<iostream> #include<cstdlib> #define MAXN 1000010 using namespace std; inline int read() { int sum=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) { sum=(sum<<1)+(sum<<3)+ch-‘0‘; ch=getchar(); } return sum; } struct Tr { int to,next,id; }c[MAXN<<1]; int head[MAXN],t; int f[MAXN],fid[MAXN],id[MAXN],l[MAXN],r[MAXN],sz,deep[MAXN]; int fa[MAXN]; inline void add(int x,int y,int z) { c[++t].to=y; c[t].next=head[x]; head[x]=t; c[t].id=z; } void dfs(int x,int FA,int FID,int d) { f[x]=FA; fid[x]=FID; id[x]=++sz; l[x]=sz; for(int i=head[x];i;i=c[i].next) if(c[i].to!=FA) { dfs(c[i].to,x,c[i].id,d+1) deep[c[i].id]=d+1; } r[x]=sz; } struct Seg_Tree { struct Node { Node *ch[2]; int l,r,mid,id; void pushdown() { ch[0]->id=deep[id]>deep[ch[0]->id]?id:ch[0]->id; ch[1]->id=deep[id]>deep[ch[1]->id]?id:ch[1]->id; } }node[MAXN<<2],*root; int sz,n; Node *New(int l,int r) { Node *x=&node[sz++]; x->l=l; x->r=r; x->mid=(l+r)>>1; return x; } void build(Node *p) { if(p->l==p->r)return; p->ch[0]=New(p->l,p->mid); p->ch[1]=New(p->mid+1,p->r); build(p->ch[0]); build(p->ch[1]); } void Init() { root=New(1,n); build(root); } void update(Node *p,int l,int r,int id) { if(p->l>=l&&p->r<=r) { p->id=deep[id]>deep[p->id]?id:p->id; return; } p->pushdown(); if(l<=p->mid)update(p->ch[0],l,r,id); if(p->mid<r)update(p->ch[1],l,r,id); } int query(Node *p,int pos) { if(p->l==p->r)return p->id; p->pushdown(); return query(pos>p->mid?p->ch[1]:p->ch[0],pos); } }YY; inline int find(int x) { return x==fa[x]?x:(fa[x]=find(fa[x])); } inline void unit(int x,int y) { fa[find(x)]=find(y); } inline void gan(int x,int y) { if(find(x)==find(y))return; if(deep[find(x)]<deep[find(y)])x^=y^=x^=y; while(deep[find(x)]>deep[find(y)]) { int X=find(x); YY.update(YY.root,l[X],r[X],fid[X]); unit(X,f[X]); } while(find(x)!=find(y)) { if(deep[find(x)]<deep[find(y)])x^=y^=x^=y; int X=find(x); YY.update(YY.root,l[X],r[X],fid[X]); unit(X,f[X]); } } int main() { freopen("wbtree.in","r",stdin); freopen("wbtree.out","w",stdout); int n=YY.n=read(); YY.Init(); int T=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); add(x,y,i); add(y,x,i); } dfs(1,0,0,0); for(int i=1;i<=n;i++)fa[i]=i; while(T--) { int opt=read(),x=read(); if(opt==1)printf("%d\n",YY.query(YY.root,id[x])); else { int y=read(); gan(x,y); } } return 0; }
BZOJ 3319 黑白树 并查集+线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。