2109. [NOIP 2015] 运输计划
★★★☆ 输入文件：transport.in 输出文件：transport.out 简单对比
时间限制：3 s 内存限制：256 MB
【题目描述】
公元 2044 年，人类进入了宇宙纪元。
L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新，L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。
如果小 P 可以*选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?
【输入格式】
第一行包括两个正整数 n、m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 1 到 n 编号。
接下来 n−1 行描述航道的建设情况，其中第 i 行包含三个整数 ai、bi 和 ti，表示第 i 条双向航道修建在 ai 与 bi 两个星球之间，任意飞船驶过它所花费的时间为 ti。 接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj 号星球。
【输出格式】
共 1 行，包含 1 个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
【样例输入】
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
【样例输出】
11
【提示】
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
【来源】
NOIP 2015 Day 2 Task 3
我的天呐 我居然开始做提高组D2T3的题了！（不敢相信）
那么这一道题的正解是树链剖分LCA +差分 +二分答案 <<听起来好麻烦的样子啊
我们先来想一个暴力（60分）的做法吧
就是首先怎么想到树链剖分求LCA的呢 很简单（今天刚学的啊）
就是题目不是要求出两个点 之间的路径以及距离吗
LCA就可以实现啊
就是比如有一个dis数组（可以看我的上一篇题解）
那么dis[a]+dis[b]-dis[lca(a,b)]就是a 和 b之间的距离啊！！
然后就是枚举一下删掉那一条边 呵呵 肯定超时 不是正解 我就不再赘述了 啊
满分做法 看起来非常玄学
树链剖分LCA +差分+二分答案
二分答案的就是 。。。就是答案啊 就是最短 的时间
首先肯定答案是满足可二分性的。。。（自己去想想吧）
然后首先求LCA 的部分就自己看代码吧
主要来讲一下怎样优化AC
首先第一个问题 二分答案怎么检验
一个很简单的想法就是 枚举每一条边 很显然这和刚才的那个暴力的做法有什么区别呢 （还更慢了）
首先有这么一个神奇的想法 就是我们不用枚举每一条边了 我们先在一开始的时候记录一个max_dis 嗯嗯嗯呃 那肯定啊 题目就是让求删掉一条边后最长的路径啊
嗯嗯 就是我们可以枚举一下每一条呗多少的路径经过 然后呢？？‘’
对于原长度大于mid的路径 假设有cnt条 其中最长的的一条长度设为max_dis
那么删去那条边 必须被这cnt天路径经过
且这条边假设长度为dis 那么要有max_dis-dis<=mid
可以用差分数组来记录一下每条边有多少路径经过（不明白的可以看一看我的另一篇 差分详解哦）
#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define maxn 300005
//#define to e[i].to
using namespace std;
int n,m;
int dis[maxn],a[maxn],size[maxn],top[maxn],son[maxn],dfn[maxn],pos[maxn],Dp[maxn],fa[maxn],mark[maxn],cnt;
struct edge{
int to;
int val;
};
vector<edge> e[maxn];
int q[maxn][],max_dis=;
void addedge(int x,int y,int z){
edge tmp;tmp.to=y;tmp.val=z;
e[x].push_back(tmp);
tmp.to=x;e[y].push_back(tmp);
}
void Dfs(int rt){
size[rt]=;
for(int i=;i<e[rt].size();i++){
int to=e[rt][i].to;
if(!size[to]){
dis[to]=dis[rt]+e[rt][i].val;
Dp[to]=Dp[rt]+;
fa[to]=rt;a[to]=e[rt][i].val;
Dfs(to);
size[rt]+=size[to];
if(size[to]>size[son[rt]]) son[rt]=to;
}
}
}
void Dfs(int rt,int tp){
top[rt]=tp;dfn[++cnt]=rt;pos[rt]=cnt;
if(son[rt]) Dfs(son[rt],tp);
for(int i=;i<e[rt].size();i++){
int to=e[rt][i].to;
if(!top[to]) Dfs(to,to);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(Dp[top[x]]<Dp[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(Dp[x]>Dp[y]) swap(x,y);
return x;
}
void beMark(int x,int y){
int s=pos[x],t=pos[y];
mark[s]++;mark[t+]--;
}
void Mark(int x,int y){
while(top[x]!=top[y]){
if(Dp[top[x]]<Dp[top[y]]) swap(x,y);
beMark(top[x],x);
x=fa[top[x]];
}
if(Dp[x]>Dp[y]) swap(x,y);
if(x!=y) beMark(son[x],y);
}
bool Check(int mid){
int tot=;
memset(mark,,sizeof(mark));
for(int i=;i<m;i++)
if(q[i][]>mid) tot++,Mark(q[i][],q[i][]);
if(!tot) return true;
for(int i=;i<=n;i++) mark[i]+=mark[i-];
for(int i=;i<=n;i++) if(mark[pos[i]]==tot&&max_dis-a[i]<=mid) return true;
return false;
}
int main()
{
// freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n-;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
}
Dfs();Dfs(,);
for(int i=;i<m;i++){
int x,y;scanf("%d%d",&x,&y);
q[i][]=x;q[i][]=y;q[i][]=dis[x]+dis[y]-*dis[lca(x,y)];
max_dis=max(max_dis,q[i][]);
}
int l=,r=max_dis,mid;
while(l<r){
mid=(l+r)>>;
if(Check(mid)) r=mid;
else l=mid+;
}
cout<<l;
return ;
}
666