欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ[3872][Poi2014]Ant colony 二分

程序员文章站 2022-07-13 12:41:27
...

传送门ber~

怎么又在刷水/糗大了
预处理每个点到问题中的边剩k个的上下界。。。
然后二分。。。。
我是卡常大师啦啦啦
把函数改成define就过了/呲牙

代码如下:

#include<algorithm>
#include<ctype.h>
#include<cstdio>
#define N 1000020
#define add(x,y) {nex[++top]=Edge(y,fir[x]);fir[x]=top;degree[x]++;}
using namespace std;
inline int read(){
    int x=0,f=1;char c;
    do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));
    do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));
    return x*f;
}
typedef long long LL;
int n,m,k,x,y,l,r,mid,fx,fy,top,cnt,ltmp,rtmp;
int degree[N],fir[N],s[N],a[N];
LL f[N],g[N],ans;
bool b[N];
struct Edge{
    int to,nex;
    Edge(){}
    Edge(int to,int nex):to(to),nex(nex){}
}nex[N<<1];
void dfs2(int x,int fa){
    bool t=false;
    for(register int i=fir[x];i;i=nex[i].nex){
        if(nex[i].to==fa) continue;
        t=true;
        dfs2(nex[i].to,x);
    }
    if(!t) s[++cnt]=x,b[x]=true;
}
void dfs(int x,int fa,LL k){
    f[x]=k;
    for(register int i=fir[x];i;i=nex[i].nex){
        if(nex[i].to==fa) continue;
        if(b[nex[i].to]) dfs(nex[i].to,x,k);
        else dfs(nex[i].to,x,min(k*(degree[nex[i].to]-1),1ll*a[m]+1));
    }
}
void dfs1(int x,int fa,LL k){
    g[x]=k;
    for(register int i=fir[x];i;i=nex[i].nex){
        if(nex[i].to==fa) continue;
        if(b[nex[i].to]) dfs1(nex[i].to,x,k);
        else dfs1(nex[i].to,x,min((k+1)*(degree[nex[i].to]-1)-1,1ll*a[m]+1));
    }
}
__attribute__((optimize("-O3"))) main(){
    n=read();m=read();k=read();
    for(register int i=1;i<=m;i++){
        a[i]=read();
    }
    sort(a+1,a+m+1);
    fx=read();fy=read();
    add(fx,fy);add(fy,fx);
    for(register int i=1;i<n-1;i++){
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs2(fx,fy);dfs2(fy,fx);
    if(b[fx]){
        dfs(fx,fy,k);
        dfs1(fx,fy,k);
    }
    else{
        dfs(fx,fy,1ll*k*(degree[fx]-1));
        dfs1(fx,fy,1ll*(k+1)*(degree[fx]-1)-1);
    }
    if(b[fy]){
        dfs(fy,fx,k);
        dfs1(fy,fx,k);
    }
    else{
        dfs(fy,fx,1ll*k*(degree[fy]-1));
        dfs1(fy,fx,1ll*(k+1)*(degree[fy]-1)-1);
    }
    for(register int i=1;i<=cnt;i++){
        l=1;r=m;ltmp=rtmp=-1;
        while(l<=r){
            mid=(l+r)>>1;
            if(a[mid]<=g[s[i]]) rtmp=mid,l=mid+1;
            else r=mid-1;
        }
        if(!~rtmp) continue;
        l=1;r=m;
        while(l<=r){
            mid=(l+r)>>1;
            if(a[mid]>=f[s[i]]) ltmp=mid,r=mid-1;
            else l=mid+1;
        }
        if(!~ltmp) continue;
        if(rtmp>=ltmp) ans=ans+1ll*k*(rtmp-ltmp+1);
    }
    printf("%lld",ans);
    return 0;
}