最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • BZOJ 3319 黑白树 并查集+线段树

    题目大意:给定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;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » BZOJ 3319 黑白树 并查集+线段树

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级