首页 > 其他 > 详细

树链剖分-CF165D Beard Graph

时间:2021-05-14 09:52:07      阅读:21      评论:0      收藏:0      [点我收藏+]

题意

  • 给定一棵 个节点的树,初始所有边都是黑边。
  • 有 m 个操作:
  • 1 u:把第 u 条边改成黑边。
  • 2 u:把第 u 条边改成白边。
  • 3 u v:若 u 号节点和 v 号节点间存在白边,输出 -1,否则输出 u 号节点和 v 号节点间的黑边数。

分析

树链剖分板子题。

询问是看u到v节点的路径间是否存在白边,一个简单的技巧就是将白边记为1,黑边记为0。如果有一条链上的和>0,说明路径上存在白色的边。

要有记得要把点权下推到同一条边上深度更大的点(常用技巧)。

 

CODE:

#include<bits/stdc++.h>
using namespace std;
int n,m,opt,x,y,cnt,tot,u[100010],v[100010],h[100010],dad[100010],top[100010],dep[100010],size[100010],son[100010],id[100010],out;
char c;
struct Edge
{
    int to,next;
}e[200010];
struct SegT
{
    int s;
}t[400010];
int read()
{
    out=0,c=getchar();
    while(c<48||c>57){c=getchar();}
    while(c>=48&&c<=57){out=(out<<3)+(out<<1)+(c&15),c=getchar();}
    return out;
}
void Add(int x,int y)
{    
    e[++cnt].next=h[x],
    e[cnt].to=y,
    h[x]=cnt;
}
void DFS1(int x)
{
    dep[x]=dep[dad[x]]+1,size[x]=1;
    for(int i=h[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y^dad[x])
        {
            dad[y]=x;
            DFS1(y);
            size[x]+=size[y],
            son[x]=size[y]>size[son[x]]?y:son[x];
        }
    }
}
void DFS2(int x) 
{
    id[x]=++tot,
    top[x]=x==son[dad[x]]?top[dad[x]]:x;
    if(!son[x]){return;}
    DFS2(son[x]);
    for(int i=h[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y^dad[x]&&y^son[x]){DFS2(y);}
    }
}
void DFS(int x)
{
    DFS1(x);
    DFS2(x);
}
void Pushup(int k)
{
    t[k].s=t[k<<1].s+t[k<<1|1].s;
}
void Change(int k,int l,int r,int p,int x)
{
    if(l==r)
    {
        t[k].s=x;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid){Change(k<<1,l,mid,p,x);}
    else{Change(k<<1|1,mid+1,r,p,x);}
    Pushup(k);
}
int Query(int k,int l,int r,int ll,int rr)
{
    if(r<ll||rr<l){return 0;}
    if(ll<=l&&r<=rr){return t[k].s;}
    int mid=l+r>>1;
    return Query(k<<1,l,mid,ll,rr)+Query(k<<1|1,mid+1,r,ll,rr);
}
int LCA(int x,int y)
{
    int ans=0,now;
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]){x^=y,y^=x,x^=y;}
        now=Query(1,1,n,id[top[x]],id[x]);
        if(now){return -1;}
        ans+=id[x]-id[top[x]]+1;
        x=dad[top[x]];
    }
    if(dep[x]>dep[y]){x^=y,y^=x,x^=y;}
    now=Query(1,1,n,id[x]+1,id[y]);
    if(now){return -1;}
    ans+=id[y]-id[x];
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)
    {
        u[i]=read(),v[i]=read();
        Add(u[i],v[i]);Add(v[i],u[i]);
    }
    DFS(1);
    m=read();
    while(m--)
    {
        opt=read();
        if(opt==1)
        {
            x=read();
            if(dep[u[x]]>dep[v[x]]){Change(1,1,n,id[u[x]],0);}
            else{Change(1,1,n,id[v[x]],0);}
        }
        if(opt==2)
        {
            x=read();
            if(dep[u[x]]>dep[v[x]]){Change(1,1,n,id[u[x]],1);}
            else{Change(1,1,n,id[v[x]],1);}
        }
        if(opt==3)
        {
            x=read(),y=read();
            printf("%d\n",LCA(x,y));
        }
    }
    return 0;
}

 

树链剖分-CF165D Beard Graph

原文:https://www.cnblogs.com/zzWutianyu/p/14766646.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!