BZOJ4326: NOIP2015 运输计划-蒲公英云

BZOJ4326: NOIP2015 运输计划

题目大意：给出一棵带边权的树和m条路径，可以将一条边的边权变成0，求问最长的路径最短是多少。

题解：

暴力算法：将每条边变不变，用数据结构维护，更新答案。

这样显然过不掉。

通常最值问题考虑贪心和二分答案，这里我们使用二分答案，二分最长的路径是多少。

假如最长路径maxn<=当前二分的值mid，那么结果显然可行。

如果maxn-mid可以通过将一条边的边权变成0来消去，即这条边的边权>=maxn-mid，那么结果也可行。

现在问题转化成：路径长度>mid的所有路径中，是否存在一条公共边，满足这条公共边的边权>=maxn-mid。

如何判断公共边呢？我们记一下每条边经过的次数，如果经过次数等于路径数，则说明这条边是公共边。

经过次数用树上查分来维护就好。

可是你会发现你会被卡常。。。

在这里给出几个优化的方法：

1.快速读入。

2.缩小l和r的范围，由于只能将一条边的边权变成0，所以左边界是最长路径maxn-最大边权tmp，右边界就是最长路径maxn。

3.有很多时间是花费在求LCA上，预处理出每条路径两个端点的LCA。

当然还有更毒瘤的优化方式，这里就不一一赘述了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<iostream>
#include<queue>
using namespace std;
#define isNum(a) (a>='0'&&a<='9')
#define SP putchar(' ')
#define EL putchar('\n')
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
template<class T1>void read(T1 &r_e_a_d);
template<class T1>void write(T1 w_r_i_t_e);
int n,m,len,x,y,z,from[300005],to[300005],head[300005];
struct EDGE{
    int to,next,num;
}edge[600005];
void add(int u,int v,int w){
    ++len;
    edge[len].to=v;
    edge[len].next=head[u];
    edge[len].num=w;
    head[u]=len;
}
int fa[300005],dep[300005],son[300005],siz[300005],dist[300005];
void dfs1(int u,int father){
    fa[u]=father;dep[u]=dep[father]+1;siz[u]=1;
    for (register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if (v!=father){
            dist[v]=dist[u]+edge[i].num;
            dfs1(v,u);
            siz[u]+=siz[v];
            if (son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}
int top[300005];
void dfs2(int u,int tp){
    top[u]=tp;
    if (son[u]==-1) return ;
    dfs2(son[u],tp);
    for (register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if (v!=fa[u]&&v!=son[u]){
            dfs2(v,v);
        }
    }
}
int LCA(int u,int v){
    while (top[u]!=top[v]){
        if (dep[top[u]]>dep[top[v]]) u=fa[top[u]];
        else v=fa[top[v]];
    }
    if (dep[u]<dep[v]) return u;
    return v;
}//树链剖分求LCA 
int tmp,maxn,l,r,mid,ans,cnt[300005],e,lca[300005],dis[300005],dif[300005];
void prepare(int u,int father){
    dif[u]=cnt[u];
    for (register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if (v!=father){
            prepare(v,u);
            dif[u]+=dif[v];
        }
    }
}
bool dfs(int u,int father,int k,int ed){
    for (register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if (v!=father){
            if (dif[v]==ed&&edge[i].num>=k) return 1;
            if (dfs(v,u,k,ed)) return 1;
        }
    }
    return 0;
}
bool check(int k){
    memset (dif,0,sizeof (dif));
    memset (cnt,0,sizeof (cnt));
    e=0;
    if (maxn<=k) return 1;
    for (register int i=1;i<=m;++i){
        if (dis[i]>k){
            ++e;
            ++cnt[from[i]];++cnt[to[i]];cnt[lca[i]]-=2;
        }
    }
    prepare(1,0);
    return dfs(1,0,maxn-k,e);
}//树上差分代码 
int main(){
    memset (son,-1,sizeof (son));
    read(n);read(m);
    for (register int i=1;i<n;++i){
        read(x);read(y);read(z);
        add(x,y,z);add(y,x,z);
        tmp=max(tmp,z);
    }
    dfs1(1,0);dfs2(1,1);
    for (register int i=1;i<=m;++i){
        read(from[i]);read(to[i]);
        lca[i]=LCA(from[i],to[i]);
        dis[i]=dist[from[i]]+dist[to[i]]-dist[lca[i]]*2;
        r=max(r,dis[i]);
    }
    maxn=r;l=r-tmp;
    while (l<=r){
        mid=l+r>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    write(ans);EL;     
    return 0;
}
template<class T1>void read(T1 &r_e_a_d){
    T1 k=0;
    char ch=getchar();
    int flag=1;
    while(!isNum(ch)){
        if(ch=='-'){
            flag=-1;
        }
        ch=getchar();
    }
    while(isNum(ch)){
        k=((k<<1)+(k<<3)+ch-'0');
        ch=getchar();
    }
    r_e_a_d=flag*k;
}
template<class T1>void write(T1 w_r_i_t_e){
    if(w_r_i_t_e<0){
        putchar('-');
        write(-w_r_i_t_e);
    }else{
        if(w_r_i_t_e<10){
            putchar(w_r_i_t_e+'0');
        }else{
            write(w_r_i_t_e/10);
            putchar((w_r_i_t_e%10)+'0');
        }
    }
}