运输计划
心路历程
我一直不太会二分答案，但是感觉做了几道01分数规划和二分答案的题有了一点理解，其实就是我们去找一个很大一个0，之后不断地去二分，看一看这个答案符不符合要求，下面讲解一下二分答案
二分答案
首先可以二分的题的答案都要满足一个要求，就是有单调性，比如这道题，假设时间T是我们二分出来的答案，并且这个答案符合这个题目，那么T+1一定可以，T-1一定不可以，这就是单调性
转移到这道题里面，不就是我们去二分一个时间t，假如所有的计划再删掉某一条边之后的最大值满足<=t, 那么这个t是合法的，我们要在往小了去找。
如何判断答案是否合法—树上差分
刚才说了是要去找最大值，但是我们发现假如有n个计划都不满足，那么我们要找的不就是这n个计划中的路径交，看看删除这些路径交，是否可以使得这n个满足二分出来的t，这个是不是一下子就想到了树上差分，并且我们在这里只打标记不去推，和边打标记边推，是差不多的复杂度（我感觉），所以我就偷懒了
lca
这个还是去看我另外一个博客吧
博客
主要是用来树上前缀和的
树上前缀和
这个是在树上去求距离的，也就是和数组一样的思想，我们再lca的dfs数组中直接完成就OK了
完整思路
这道题的完整解法就是去二分一个完成任务时间的最大值，看一看这个时间是否合法，合法就往小了去找，不合法就往大了去找，最后利用lca和树上前缀和去加速
代码
#include<bits/stdc++.h>
using namespace std;inline int read(){
int r=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') r=(r<<3)+(r<<1)+ch-'0',ch=getchar();return r;
}int n,m;//星球数量，和轨道个数
int num=0,head[600005],to[600005],nex[600005],val[600005];
void add(int x,int y,int z){
to[++num]=y;nex[num]=head[x];head[x]=num;val[num]=z;
}
int fa[300005][30];
int dep[300005],dis[300005],llog[300005];
void dfs(int x,int y,int wa){
dep[x]=wa;fa[x][0]=y;for(int i=1;(1<<i)<=dep[x];i++) fa[x][i]=fa[ fa[x][i-1] ][i-1];//这句话有点容易忘for(int i=head[x];i;i=nex[i]){
if(to[i]==y) continue;if(to[i]!=y){
dis[to[i]]=dis[x]+val[i];//树上前缀和 dfs(to[i],x,wa+1);}}
}int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);while(dep[x]>dep[y]) x=fa[x][ llog[dep[x]-dep[y]]-1];if(x==y) return x;for(int i=llog[dep[x]]-1;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i],y=fa[y][i];}}return fa[x][0];
}
struct plan{
int x;int y;int lcaa;int far;
};
plan did[300005];bool cmp(plan x,plan y){
return x.far<y.far;
}
void init(){
int a,b;for(int i=1;i<=m;i++){
did[i].x=read();did[i].y=read();did[i].lcaa=lca(did[i].x,did[i].y);did[i].far=dis[did[i].x]+dis[did[i].y]-2*dis[did[i].lcaa];}sort(did+1,did+1+m,cmp);//之后check会好一点
}//对于每一个计划的预处理 int sum[300005];//树上差分数组
bool check(int x){
if(did[m].far<=x) return true;memset(sum,0,sizeof(sum));int cnt=0,maxn=0;for(int i=m;i>0;i--){
if(did[i].far<=x) break;cnt++;int f=did[i].x,t=did[i].y,p=did[i].lcaa,lg=did[i].far-x;while(f!=p){
if(dis[f]-dis[fa[f][0]]>=lg){
//只要这条路删掉可以使得在这个道路符合条件，就去差分，并且往上跳sum[f]++;maxn=maxn<sum[f]?sum[f]:maxn; }f=fa[f][0];}while(t!=p){
if(dis[t]-dis[fa[t][0]]>=lg){
sum[t]++;maxn=sum[t]>maxn?sum[t]:maxn;}t=fa[t][0];}if(maxn<cnt) return false;//如果找不到每一条路径的交使得这几条路都欧克，那肯定就不欧克 }return true;
}void get_ans(){
int l=0,r=300000000,ans=0;while(l<r){
int mid=(l+r)>>1;if(check(mid)) {
r=mid,ans=mid;}else l=mid+1;} printf("%d",ans);
} int main(){
n=read(),m=read();int a,b,c;for(int i=1;i<n;i++){
a=read(),b=read(),c=read();add(a,b,c);add(b,a,c);} dfs(1,0,1);for(int i=1;i<=n;i++){
llog[i]=llog[i-1]+(1<<llog[i-1]==i);}init();//初始化每一个计划get_ans();return 0;
}总结加立flag
其实树剖也可以去求lca，并且比较快，所以以后我还要去补上树剖的代码，最后还有就是有机会的话，再去复习一下二分的例题《跳石头》，最后就这样了，这一道题可以写出来真的很开心