BZOJ4326: NOIP2015 运输计划

佚名 6年前 (2019-04-23) 随笔 1028人围观抢沙发百度已收录

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

题解：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

这样显然过不掉。

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

假如最长路径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');
        }
    }
}