BZOJ 3319 黑白树 并查集+线段树
来源：程序员人生 发布时间：2015-04-09 09:11:16 阅读次数：2764次
题目大意：给定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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
