BZOJ 3319 黑白樹 并查集+線段樹
來源：程序員人生 發布時間：2015-04-09 09:11:16 閱讀次數：2905次
題目大意：給定1棵樹，有兩種操作：
1.詢問某個點到根的路徑上遇到的第1個黑色邊的編號
2.將某條路徑涂黑
首先將每條邊歸到它下面的點上
記錄每一個點到根路徑上深度最大的斑點
那末將1個點涂黑就相當于把子樹中所有的點的最深斑點取個max
這個用線段樹就能夠保護
由于1個點最多只會被涂黑1次 因此時間復雜度是O(nlogn)的
現在問題就是如何在每次修改時找到路徑上所有白點
這個用并查集就能夠弄了
如果1個點被涂黑 那末就把這個點在并查集中向父節點連1條邊
然后依照樹鏈剖分那種做法就能夠了
總時間復雜度O(nlogn)
加了讀入優化以后跑了9888ms
正解難道是線性做法？不明- -
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1001001
using namespace std;
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot=1;
int n,m;
int fa[M],dpt[M],num[M],st[M],ed[M];
void Add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x)
{
static int T;
int i;
st[x]=++T;
dpt[x]=dpt[fa[x]]+1;
for(i=head[x];i;i=table[i].next)
if(table[i].to!=fa[x])
{
fa[table[i].to]=x;
num[table[i].to]=i>>1;
DFS(table[i].to);
}
ed[x]=T;
}
bool Compare(int x,int y)
{
return dpt[x]<dpt[y];
}
struct Segtree{
Segtree *ls,*rs;
int max_dpt_point;
Segtree()
{
ls=rs=0x0;
max_dpt_point=0;
}
void Build_Tree(int x,int y)
{
int mid=x+y>>1;
if(x==y) return ;
(ls=new Segtree)->Build_Tree(x,mid);
(rs=new Segtree)->Build_Tree(mid+1,y);
}
void Modify(int x,int y,int l,int r,int val)
{
int mid=x+y>>1;
if(x==l&&y==r)
{
max_dpt_point=max(max_dpt_point,val,Compare);
return ;
}
if(r<=mid) ls->Modify(x,mid,l,r,val);
else if(l>mid) rs->Modify(mid+1,y,l,r,val);
else ls->Modify(x,mid,l,mid,val) , rs->Modify(mid+1,y,mid+1,r,val);
}
int Get_Point(int x,int y,int pos)
{
int mid=x+y>>1;
if(x==y) return max_dpt_point;
if(pos<=mid)
return max(ls->Get_Point(x,mid,pos),max_dpt_point,Compare);
else
return max(rs->Get_Point(mid+1,y,pos),max_dpt_point,Compare);
}
}*tree=new Segtree;
namespace Union_Find_Set{
int belong[M];
int Find(int x)
{
if(!belong[x]||belong[x]==x)
return belong[x]=x;
return belong[x]=Find(belong[x]);
}
}
void Modify(int x,int y)
{
using namespace Union_Find_Set;
x=Find(x);y=Find(y);
while(x!=y)
{
if(dpt[Find(fa[x])]<dpt[Find(fa[y])])
swap(x,y);
tree->Modify(1,n,st[x],ed[x],x);
belong[x]=fa[x];x=Find(x);
}
}
namespace IStream{
#define L (1<<15)
char Get_Char()
{
static char buffer[M],*S,*T;
if(S==T)
{
T=(S=buffer)+fread(buffer,1,L,stdin);
if(S==T) return EOF;
}
return *S++;
}
int Get_Int()
{
int re=0;
char c=0;
while(c<'0'||c>'9')
c=Get_Char();
while(c>='0'&&c<='9')
re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
}
int main()
{
using namespace Union_Find_Set;
using namespace IStream;
int i,p,x,y;
cin>>n>>m;
for(i=1;i<n;i++)
{
x=Get_Int();
y=Get_Int();
Add(x,y);Add(y,x);
}
DFS(1);
tree->Build_Tree(1,n);
for(i=1;i<=m;i++)
{
p=Get_Int();
if(p==1)
x=Get_Int(),printf("%d
",num[tree->Get_Point(1,n,st[x])]);
else
x=Get_Int(),y=Get_Int(),Modify(x,y);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
