题解 CF165D 【Beard Graph】

思路：将黑边标记为1，白边标记为100000，树链剖分
如果查询时ans超过100000，那就有白边，输出-1，不然直接输出ans
#include<bits/stdc++.h>

#define maxn 800001

#define int long long

#define L(x) (x<<1)

#define R(x) ((x<<1)|1)

using namespace std;

int tree[maxn],tag[maxn];

int rev[maxn],dep[maxn],size[maxn],seg[maxn],top[maxn],son[maxn],father[maxn];

int n,m,root,x,y,z,a[maxn],tot,mode;

int cnt,from[maxn],to[maxn],Next[maxn],head[maxn];

int Gx,Gy,Gz,Gd;

int fa[maxn],X[maxn],Y[maxn],Z[maxn];

void add(int x,int y){

    cnt++;

    from[cnt]=x;to[cnt]=y;

    Next[cnt]=head[x];head[x]=cnt;

}

void update(int node,int begin,int end,int x,int y,int val){

    if(begin>y||end<x)return;

    if(begin>=x&&end<=y){

        tree[node]=val;

        return;

    }else{

        int mid=(begin+end)>>1;

        if(x<=mid)update(L(node),begin,mid,x,y,val);

        if(y>mid) update(R(node),mid+1,end,x,y,val);

        tree[node]=tree[L(node)]+tree[R(node)];

    }

}

int query(int node,int begin,int end,int x,int y){

    if(begin>=x&&end<=y){

        return tree[node];

    }else{

        int mid=(begin+end)>>1,sum=0;

        if(x<=mid)sum+=query(L(node),begin,mid,x,y);

        if(y>mid) sum+=query(R(node),mid+1,end,x,y);

        return sum;

    }

}

int dfs1(int x){

    size[x]=1;

    dep[x]=dep[father[x]]+1;

    for(int i=head[x];i!=-1;i=Next[i]){

        int v=to[i],big=0;

        if(father[x]==v)continue;

        father[v]=x;

        big=dfs1(v);

        size[x]+=big;

        if(big>size[son[x]])son[x]=v;

    }

    return size[x];

}

void dfs2(int x){

    if(son[x]){

        seg[son[x]]=++seg[0];

        top[son[x]]=top[x];

        rev[seg[0]]=son[x];

        dfs2(son[x]);

    }

    for(int i=head[x];i!=-1;i=Next[i]){

        int v=to[i];

        if(!top[v]){

            seg[v]=++seg[0];

            top[v]=v;

            rev[seg[0]]=v;

            dfs2(v);

        }

    }

}

int linkquery(int x,int y){

    int fx=top[x],fy=top[y],ans=0;

    while(fx!=fy){

        if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);

        ans+=query(1,1,seg[0],seg[fx],seg[x]);

        x=father[fx];fx=top[x];

    }

    if(dep[x]>dep[y])swap(x,y);

    ans+=query(1,1,seg[0],seg[x],seg[y]);

    ans-=query(1,1,seg[0],seg[x],seg[x]);

    return ans;

}

void change(int x,int y){

    x*=2;

    x=dep[from[x]]>dep[to[x]]?from[x]:to[x];

    update(1,1,seg[0],seg[x],seg[x],y);

}

signed main(){

    memset(head,-1,sizeof(head));

    scanf("%lld",&n);root=1;

    for(int i=1;i<=n-1;i++){

        scanf("%lld%lld",&x,&y);

        add(x,y),add(y,x);

    }

    dfs1(root);

    seg[root]=++seg[0];

    rev[seg[0]]=root;

    top[root]=root;

    dfs2(root);

    scanf("%lld",&m);

    for(int i=1;i<=n-1;i++)change(i,1);

    for(int i=1;i<=m;i++){

        scanf("%lld%lld",&mode,&x);

        if(mode==1)change(x,1);

        if(mode==2)change(x,100000);

        if(mode==3){

            scanf("%lld",&y);

            int ans=0;

            ans=linkquery(x,y);

            if(ans>=100000)printf("-1\n");else

            printf("%lld\n",ans);

        }

    }

}
巴特西

题解 CF165D 【Beard Graph】

最新文章

热门文章
