P2680 运输计划 二分+树上差分

又咕咕了几天\(QwQ\)

---

思路：二分+树上差分

提交：\(\geq5\)次

错因：\(lca\)写错+卡了很久常数（哪位大佬帮我康康，有更好的写法请指出\(QwQ\)）

题解：

我们先将原问题转化为\(log_2n\)个判定问题；

如何\(ck(x)\)：把所有\(>x\)的路径在树上标记（边差分），然后找到被所有\(>x\)路径覆盖的点（边转点，边权下放点权）,尝试把这个点的权值改为零，检查最长路径的时间是否\(\leq x\).

若存在这样的点，\(return\ true\)，否则\(return\ false\).

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define ull unsigned long long

#define ll long long

#define R register int

using namespace std;

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[1<<15],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline int g() {

	R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;

	if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}

inline void gs(char* s) {

	register char ch; while(isempty(ch=getchar()));

	do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

const int N=300010;

struct edge {

	int u,v,w;

}e[N];

int n,m,cnt,mx;

int vr[N<<1],nxt[N<<1],w[N<<1],W[N],fir[N],d[N],dis[N],f[N][20],c[N],s[N],lg[N];

inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;}

inline void dfs(int u) {

	for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

		if(d[v]) continue; W[v]=w[i];

		f[v][0]=u; R p=u; d[v]=d[u]+1; dis[v]=dis[u]+w[i];

		for(R j=0;f[p][j];++j) f[v][j+1]=f[p][j],p=f[p][j];

		dfs(v);

	}

}

inline int lca(int u,int v) {

	if(d[u]<d[v]) swap(u,v); R lim=log2(d[u])+1;

	for(R i=lim;~i;--i) if(d[f[u][i]]>=d[v]) u=f[u][i];

	if(u==v) return u;

	for(R i=lim;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];

	return f[u][0];

}

inline bool ck(int x) { R tot=0;

	memset(c,0,sizeof(c));

	for(R i=1;i<=m;++i) if(e[i].w>x)

		++tot,++c[e[i].u],++c[e[i].v],c[lca(e[i].u,e[i].v)]-=2;

	for(R i=1;i<=n;++i) c[f[s[i]][0]]+=c[s[i]];

	for(R i=n;i>=1;--i) if(tot==c[i]&&mx-W[i]<=x) return true;

	return false;

}

inline bool cmp(const int& a,const int& b) {return d[a]>d[b];}

inline void main() {

	n=g(),m=g();

	for(R i=1,u,v,w;i<n;++i)

		u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);

	d[1]=1; dfs(1);

	for(R i=1;i<=n;++i) s[i]=i; sort(s+1,s+n+1,cmp);

	for(R i=1;i<=m;++i) {

		e[i].u=g(),e[i].v=g();

		e[i].w=dis[e[i].u]+dis[e[i].v]-2*dis[lca(e[i].u,e[i].v)];

		mx=max(mx,e[i].w);

	} R l=0,r=mx+1;

	while(l<r) {

		R md=l+r>>1;

		if(ck(md)) r=md;

		else l=md+1;

	} printf("%d\n",l);

}

}

signed main() {

	Luitaryi::main();

	return 0;

}

---

2019.07.25