2018.09.26 bzoj4326: NOIP2015 运输计划（二分+树上差分）

传送门

简单树上操作。

先转边权为点权。

显然所有的询问操作对应的路径会有一些交点，那么我们可以直接二分答案，对于所有大于二分值的询问用树上差分维护，最后dfs一遍每个点被覆盖了几次，当前情况合法当且仅当被覆盖次数与大于二分值的询问数相同且点权值可以使跟二分值相比差最大的询问合法。

代码：

#include<bits/stdc++.h>
#define N 300005
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int n,m,first[N],cnt=0,dis[N],fa[N],top[N],tim[N],dep[N],siz[N],hson[N],val[N],tot=0;
struct edge{int v,next,w;}e[N<<1];
struct Q{int u,v,t,w;}q[N<<1];
inline void add(int u,int v,int w){e[++cnt].v=v,e[cnt].next=first[u],e[cnt].w=w,first[u]=cnt;}
inline void dfs1(int p){
	siz[p]=1;
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa[p])continue;
		dis[v]=e[i].w+dis[p],val[v]=e[i].w,fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
		if(siz[v]>siz[hson[p]])hson[p]=v;
	}
}
inline void dfs2(int p,int tp){
	top[p]=tp;
	if(!hson[p])return;
	dfs2(hson[p],tp);
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v!=hson[p]&&v!=fa[p])dfs2(v,v);
	}
}
inline void dfs3(int p){
	for(int i=first[p];i;i=e[i].next){
		if(e[i].v==fa[p])continue;
		dfs3(e[i].v),tim[p]+=tim[e[i].v];
	}
}
inline void update(int i){++tim[q[i].u],++tim[q[i].v],tim[q[i].t]-=2;}
inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
inline bool check(int mid){
	int mx=0,pot=0;
	memset(tim,0,sizeof(tim));
	for(int i=1;i<=m;++i)if(q[i].w>mid)update(i),mx=max(mx,q[i].w-mid),++pot;
	dfs3(1);
	for(int i=1;i<=n;++i)if(tim[i]>=pot&&val[i]>=mx)return true;
	return false;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	dfs1(1),dfs2(1,1);
	int l=0,r=0,ans=0;
	for(int i=1;i<=m;++i){
		q[i].u=read(),q[i].v=read();
		q[i].t=lca(q[i].u,q[i].v),q[i].w=dis[q[i].u]+dis[q[i].v]-2*dis[q[i].t],r=max(r,q[i].w);
	}
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}

2018.09.26 bzoj4326: NOIP2015 运输计划（二分+树上差分）的相关教程结束。