CF165D Beard Graph

青旅半醒 2023-06-04 08:00 8阅读 0赞

[**题目链接**][Link 1]

**树剖题不用多说，一开始所有黑边的权值是-1，若有修改白边的操作，就把白边的值赋为100000。**

**之后查询边权之和时，如果和大于1000000，就肯定存在白边，直接输出-1。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//做法：树剖，一开始黑边边权全设为1，若有修改白边，设为100000
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int nxt,to,val,from;
    }edge[maxn*4];
    int head[maxn],cnt;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].from=x;
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    int n,m;
    int x,y;
    int opt,num;
    int dep[maxn],fa[maxn],size[maxn],son[maxn],w[maxn];
    void dfs1(int x,int f){
        fa[x]=f;
        size[x]=1;
        dep[x]=dep[f]+1;
        int maxson=-1;
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[x]) continue;
            w[v]=edge[i].val;
            dfs1(v,x);
            size[x]+=size[v];
            if(size[v]>maxson){
                maxson=size[v];
                son[x]=v;
            }
        }
    }
    int id[maxn],top[maxn],va[maxn],Time;
    void dfs2(int x,int topf){
        top[x]=topf;
        id[x]=++Time;
        va[id[x]]=w[x];
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[x]||v==son[x]) continue;
            dfs2(v,v);
        }
    }
    struct nod{
        int l,r;
        long long sum;
        int lazy;
    }tree[maxn*4];
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r,tree[now].lazy=-1;
        if(l==r){
            tree[now].sum=va[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    void pushdown(int now){
        if(tree[now].lazy!=-1){
            tree[now<<1].sum=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].lazy;
            tree[now<<1|1].sum=(tree[now<<1|1].r-tree[now<<1|1].r+1)*tree[now].lazy;
            tree[now<<1].lazy=tree[now].lazy;
            tree[now<<1|1].lazy=tree[now].lazy;
            tree[now].lazy=-1;
        }
    }
    void update(int now,int l,int r,int v){
        if(tree[now].l>=l&&tree[now].r<=r){
            tree[now].sum=(tree[now].r-tree[now].l+1)*v;
            tree[now].lazy=v;
            return;
        } 
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) update(now<<1,l,r,v);
        if(r>mid) update(now<<1|1,l,r,v);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    long long query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        long long val=0;
        if(l<=mid) val+=query(now<<1,l,r);
        if(r>mid) val+=query(now<<1|1,l,r);
        return val;
    }
    long long link(int x,int y){
        long long ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans+=query(1,id[top[x]],id[x]);
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        ans+=query(1,id[y]+1,id[x]);
        return ans;
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            add(x,y,1);add(y,x,1);
        }
        scanf("%d",&m);
        dfs1(1,0);
        dfs2(1,1);
        build(1,1,n);
        for(int i=1;i<=m;i++){
            scanf("%d",&opt);
            if(opt==2){
                scanf("%d",&num);
                int s=edge[num*2].from;
                int t=edge[num*2].to;
                if(dep[s]>dep[t]) swap(s,t);
                update(1,id[t],id[t],1000000);
            } 
            else if(opt==1){
                scanf("%d",&num);
                int s=edge[num*2].from;
                int t=edge[num*2].to;
                if(dep[s]>dep[t]) swap(s,t);
                update(1,id[t],id[t],1);
            }
            else{
                scanf("%d%d",&x,&y);
                if(link(x,y)>=1000000) printf("-1\n");
                else printf("%lld\n",link(x,y));
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11432154.html

[Link 1]: https://www.luogu.org/problem/CF165D
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a85372b237dd475197aa34781c705a69.png