[NOIP2015]运输计划

题目（vijos）
来说说这题怎么做吧
首先，最简单的，暴力枚举每条边，再跑路径，完毕。
：）
然后，考虑这是一棵树，路径唯一，所以可以用个树剖什么的。
：>
之后来到正解（95分）！
首先，求树上两点路径长度，不错的做法就是用LCA，求出(l,r)两点的lca，然后路径长度就是：
dis[l]+dis[r]-(dis[lca]<<1);
同时，用一个数组leng记录当前点与其父亲之间的边的权值。
然后有m个(l,r)，所以lca必然是首选，并且将每个运输计划用结构体state保存（见代码）。
这道题最多只改变一条边的权值，并让最大值最小，怎么办？
妥妥的二分答案啊！
二分答案，check当前mid是否可行，
可以的话，ans=mid,R=mid-1，不行的话，L=mid+1
最后输出答案，完毕。

---

接下来考虑怎么check。
对于这很多个运输计划，很有可能会出现这种情况：

3->4这条边我们称之为“交边”。
可以看出，如果每次check都删除交边，可以使答案更优。
那么要求哪些运输计划的交边呢？这与mid有关。
只要当前运输计划的时间<=mid，那么就不管；
如果大于，那么就求树上每条边被这些大于mid的运输计划经过了多少次。
然后怎么求交边呢？运用到一个知识点：差分求交。
用一个cnt记录一共有多少个运输计划大于mid，
用一个maxn表示哪个运输计划减去mid的花费时间最大，
这样，将其删掉后使解更优。
所以，return true的条件有两个：
1.c[i]==cnt
2.leng[i]>=maxn
否则return false。
另外，每次check都要初始化c为0。
完毕。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template  inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int L,R,mid;
int n,m;
struct edge{
	int vk;
	int wk;
	int nxt;
}e[600005];
int t,head[300005];
void ad(int u,int v,int w)
{
	e[++t].vk=v;
	e[t].wk=w;
	e[t].nxt=head[u];
	head[u]=t;
}
int dis[300005],p[300005][20];
int leng[300005];
int dep[300005];
int c[300005];
struct state{
	int l,r;
	int lca,len;
}a[300005];
void dfslca(int u)
{
	for (int i=1;i<=18;++i)
		p[u][i]=p[p[u][i-1]][i-1];
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		int w=e[i].wk;
		if (v==p[u][0]) continue;
		dis[v]=dis[u]+w;
		p[v][0]=u;
		dep[v]=dep[u]+1;
		leng[v]=w;
		dfslca(v);
	}
}
inline int lca(int x,int y)
{
	if (dep[x]>dep[y]) swap(x,y);
	for (int i=18;i>=0;--i)
	{
		if (dep[y]-(1<=0;--i)
	{
		if (p[x][i]==p[y][i]) continue;
		x=p[x][i],y=p[y][i];
	}
	return p[y][0];
}
void dfs(int u)
{
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==p[u][0]) continue;
		dfs(v);
		c[u]+=c[v];
	}
}
inline bool check()
{
	int maxn=0,cnt=0;
	memset(c,0,sizeof c);
	for (int i=1;i<=m;++i)
	{
		if (a[i].len>mid)
		{
			++cnt;
			++c[a[i].l],++c[a[i].r];
			c[a[i].lca]-=2;
			maxn=max(maxn,a[i].len-mid);
		}
	}
	dfs(1);
	for (int i=1;i<=n;++i)
		if (leng[i]>=maxn && c[i]==cnt)
			return true;
	return false;
}
int main()
{
	read(n),read(m);
	for (register int i=1;i<n;++i)
	{
		int x,y,z;
		read(x),read(y),read(z);
		ad(x,y,z),ad(y,x,z);
	}
	dfslca(1);
	for (register int i=1;i<=m;++i)
	{
		read(a[i].l),read(a[i].r);
		a[i].lca=lca(a[i].l,a[i].r);
		a[i].len=dis[a[i].l]+dis[a[i].r]-(dis[a[i].lca]<<1);
		R=max(R,a[i].len);
	}
	int ans=0;
	while (L<=R)
	{
		mid=(L+R)>>1;
		if (check()) ans=mid,R=mid-1;
		else L=mid+1;
	}
	printf(
	return 0;
}

为什么只有95分？
原因出在求LCA上。
这里的话用tarjan离线求LCA要比倍增快一些，
不过考虑的某些oj的评测机很棒，结果还是A了233
然而codevs就不会A掉，最后一个点始终TLE。
所以还是用tarjan离线求吧。