这题在洛谷上可以找到提交
P2680运输计划
题目背景
公元 2044 年,人类进入了宇宙纪元。
题目描述
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?
输入输出格式
输入格式：
输入文件名为 transport.in。
第一行包括两个正整数 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的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
输入样例#1：
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
输出样例#1：
11
说明
n,m<=300000
这是一棵树上距离的问题
解答分两个部分：
1、求出给出各点对之间的距离
2、将一条边权减为0使得最大距离最小
树上距离一看就自然想到了【树链剖分+树状数组（或线段树）】，先树剖给点编号，然后套用树状数组结合LCA的算法求出点对距离，1问秒掉
关键是第二问，如何删。
容易想到要选的边一定在最长的路径上，但选最长路径上最长的边不一定是对的，因为第二长的边可能与第一长的边有公共边且不相差多少，但是删去了一个非公共边就错了。
看到最大最小，自然想到二分答案：
我们二分虫洞后最长的边的长度，对于每一个check(m),只需枚举所有比m大的路径，这些路径都得缩短，将这k条路径上每一条边+1，这样一来加到了k的那些边就是所有边的公共边，再看一看他们能不能通过减为0而使这k条边都小于m。
具体怎么维护每条边加了几次，用线段树？
这样二分nlognlogn的复杂度，还是不太放心
鉴于所有的询问都是单点且都在修改之后，我们可以用差分数组以O(n)的总复杂度求出
总1044ms，还是挺优秀的效率
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lbt(x) (x&-x)
using namespace std;
const int maxn=300005,INF=2000000000; inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
} int N,M,root,rtm=INF,Maxw;
//这块是存边【链式前向星】
int head[maxn],nedge=0;
struct EDGE{
int to,w,next;
}edge[2*maxn]; inline void build(int a,int b,int w){
edge[nedge]=(EDGE){b,w,head[a]};
head[a]=nedge++;
edge[nedge]=(EDGE){a,w,head[b]};
head[b]=nedge++;
} struct node{
int a,b,w;
}p[maxn]; inline bool operator <(const node& a,const node& b){
return a.w>b.w;
}
//这块求重心
int Siz[maxn];
void dfs(int u,int f){
int to,Max=-1,Min=INF;
Siz[u]=1;
for(int k=head[u];k!=-1;k=edge[k].next)
if((to=edge[k].to)!=f){
dfs(to,u);
Siz[u]+=Siz[to];
if(Siz[to]>Max) Max=Siz[to];
else if(Siz[to]<Min) Min=Siz[to];
}
if(N-Siz[u]>Max) Max=N-Siz[u];
else if(N-Siz[u]<Min) Min=N-Siz[u];
if(Max!=-1&&Min!=INF&&Max-Min<rtm){
root=u;
rtm=Max-Min;
}
}
//这块是树链剖分
int top[maxn],siz[maxn],fa[maxn],son[maxn],id[maxn],Hash[maxn],dep[maxn],V[maxn],cnt=0; void dfs1(int u,int f,int d){
int to;
siz[u]=1;fa[u]=f;dep[u]=++d;
for(int k=head[u];k!=-1;k=edge[k].next)
if((to=edge[k].to)!=f){
dfs1(to,u,d);
V[to]=edge[k].w;
siz[u]+=siz[to];
if(!son[u]||siz[son[u]]<siz[to]) son[u]=to;
}
} void dfs2(int u,int flag){
int to;
id[u]=++cnt;Hash[cnt]=u;
flag ? top[u]=top[fa[u]]:top[u]=u;
if(son[u]) dfs2(son[u],1);
for(int k=head[u];k!=-1;k=edge[k].next)
if((to=edge[k].to)!=son[u]&&to!=fa[u])
dfs2(to,0);
}
//这块是树状数组
int A[maxn]; inline void add(int u,int v){while(u<=N){A[u]+=v;u+=lbt(u);}} inline int Sum(int u){int ans=0;while(u>0){ans+=A[u];u-=lbt(u);}return ans;} inline int Query(int l,int r){return Sum(r)-Sum(l-1);} inline void init(){for(int i=1;i<=N;i++) add(id[i],V[i]);} int solve(int u,int v){ //求路径长
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ans+=Query(id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
return ans+Query(id[u]+1,id[v]);
} int D[maxn]; //差分数组 inline void update(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
D[id[top[u]]]+=1;
D[id[u]+1]-=1;
u=fa[top[u]];
}
if(dep[u]>dep[v]) u^=v^=u^=v;
D[id[u]+1]+=1;
D[id[v]+1]-=1;
} bool check(int m){
int tot=0,v=0;
while(p[tot+1].w>m){
++tot;
update(p[tot].a,p[tot].b);
}
for(int i=1;i<=N;i++){
v+=D[i];D[i]=0;
if(v==tot&&Maxw-V[Hash[i]]<=m){
for(int j=i+1;j<=N;j++) D[j]=0;
return true;
}
}
return false;
} int main()
{
fill(head,head+maxn,-1);
N=read();
M=read();
int a,b,w,L=0,R=0;
for(int i=1;i<N;i++){
a=read();
b=read();
w=read();
build(a,b,w);
}
dfs(1,0); //求出重心作为根
dfs1(root,0,0); //dfs1、dfs2树链剖分
dfs2(root,0);
init(); //初始化树状数组
for(int i=1;i<=M;i++){
p[i].a=read();
p[i].b=read();
p[i].w=solve(p[i].a,p[i].b);
if(p[i].w>R) R=p[i].w;
}
sort(p+1,p+1+M); //路径排个序
Maxw=R;
while(L<R){ //二分答案
int mid=(L+R)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
cout<<L<<endl;
return 0;
}