NOIP2015 P2680 運輸計劃

傳送門（洛谷）

算 法 : 樹 鍊 剖 分 ， 最 近 公 共 祖 先 ， 差 分 ， 二 分 答 案 算法:樹鍊剖分，最近公共祖先，差分，二分答案 算法:樹鍊剖分，最近公共祖先，差分，二分答案

解題思路：

樹剖剖出每一個點到根的距離用 d i s [ u ] dis[u] dis[u]表示 u u u到根距離。

找到每對點的LCA，并算出距離，用 d [ i ] d[i] d[i]表示第 i i i組資料中兩點距離

二分答案 m i d mid mid作為最大邊長，找出有多少個 d [ i ] d[i] d[i]大于 m i d mid mid

再從所有大于 m i d mid mid的邊中删除一條邊，使得 m a x ( d [ i ] ) max(d[i]) max(d[i])減去這條邊後小于 m i d mid mid

Code

/****************************************
*	Problem 運輸計劃
*	Time 2019.9.5
*	User mzg1824_TY
*	Algrothim 樹鍊剖分 最近公共祖先 差分 二分
*****************************************/ 
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define don(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int maxn=3e5+10;
const int maxm=1e3+10;
int n,m,cnt;
int head[maxn],w[maxn];
int f[maxn],size[maxn],id[maxn],son[maxn],top[maxn],wt[maxn],dep[maxn];
int dis[maxn],lca[maxn],maxx,maxx1,a[maxn],b[maxn],d[maxn],topre[maxn];

template <class t> inline void read(t &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

struct node{
	int v,w,nex;
}e[maxn<<1];

void add(int u,int v,int w) {
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void readdata() {
	read(n);read(m);
	rep(i,1,n-1) {
		int x,y,z;
		read(x),read(y);read(z);
		add(x,y,z);
		add(y,x,z);
		maxx1=max(maxx1,z);
	}
}

void dfs1(int u,int fa,int deep) {
	size[u]=1;
	dep[u]=deep;
	f[u]=fa;
	int maxson=-1;
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		dis[v]=dis[u]+w;
		topre[v]=e[i].w;
		dfs1(v,u,deep+1);
		size[u]+=size[v];
		if(size[v]>maxson) {
			maxson=size[v];
			son[u]=v;
		}
	}
}

void dfs2(int u,int topf) {
	id[u]=++cnt;
	wt[cnt]=u;
	top[u]=topf;
	if(!son[u]) return;
	dfs2(son[u],topf);
	for(int i=head[u];i;i=e[i].nex) {
		int v=e[i].v;
		if(v==son[u] || v==f[u]) continue;
		dfs2(v,v);
	}
}

inline int LCA(int x,int y) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}

bool check(int k) {
	cnt=0;
	memset(w,false,sizeof(w));
	rep(i,1,m) {
		if(d[i]>k) {
			w[a[i]]++;w[b[i]]++;w[lca[i]]-=2;
			cnt++;
		}
	}
	don(i,n,1) {
		w[f[wt[i]]]+=w[wt[i]];
		if(topre[wt[i]]>=maxx-k && w[wt[i]]==cnt) return true;
	}
	return false;
}

inline int Binary_serch(int l,int r) {
	int ans=0;
	while(l<r) {
		int mid=(l+r)/2;
		if(check(mid)) {
			r=mid;ans=mid;
		}
		else l=mid+1;
	}
	return ans;
}

void work() {
	cnt=0;
	dfs1(1,0,1);
	dfs2(1,1);
	int ans=0;
	rep(i,1,m) {
		read(a[i]),read(b[i]);
		lca[i]=LCA(a[i],b[i]);
		d[i]=dis[a[i]]+dis[b[i]]-2*dis[lca[i]];
		maxx=max(maxx,d[i]);
	}
	printf("%d\n",Binary_serch(maxx-maxx1,maxx+1));
}

int main() {
	freopen("input.txt","r",stdin);
	readdata();
	work();
	return 0;
}