【Luogu】P2680运输计划（树上差分+二分）

　　题目链接

　　总体思路……怎么说呢……是个暴力吧……

　　首先用倍增预处理出每条路径的长度。　　然后按长度把路径排序。

　　然后二分答案。对于当前答案mid检验，怎么检验呢？

　　首先差分把所有长度比mid大的链上除了LCA之外的所有点权+1。dfs求出每个点的点权，顺便记下有多少点是被所有路径经过的。对于这些点，如果有一个点使得它到他的父亲那条边被删掉后，长度最长的路径都能卡过mid，那么返回true.

　　那么检查所有点发现长度最长的路径卡不过mid，那么返回false。

　　然后这题搞完了。

　　

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>

using namespace std;
int n,m;

inline int read(){
    int num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

struct Edge{
    int next,to,dis;
}edge[1000010];
int head[1000100],num;
inline void add(int from,int to,int dis){
    edge[++num]=(Edge){head[from],to,dis};
    head[from]=num;
}
struct Node{
    int from,to,dis,lca;
    bool operator <(const Node &a)const{
        return dis>a.dis;
    }
}q[300020];
int s[400020][20],d[400020][20];
int deep[400020];
int vis[300020],e[300020];
int pos[1001001],tot;
int Max,ans;

void find(int x,int fa){
    deep[x]=deep[fa]+1;
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==fa)    continue;
        s[to][0]=x;d[to][0]=edge[i].dis;find(to,x);
    }
}

void dfs(int x,int fa,int size){
    e[x]=vis[x];
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==fa)    continue;
        dfs(to,x,size);
        e[x]+=e[to];
    }
    if(e[x]==size)    pos[++tot]=x;
}

bool check(int limit){
    memset(vis,0,sizeof(vis));
    int size=0;tot=0;
    for(int i=1;i<=m;++i){
        if(q[i].dis<=limit)    break;
        vis[q[i].from]++;vis[q[i].to]++;vis[q[i].lca]-=2;
        size++;
    }
    dfs(1,1,size);
    for(int i=1;i<=tot;++i)
        if(q[1].dis-d[pos[i]][0]<=limit)    return 1;
    return 0;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<n;++i){
        int from=read(),to=read(),dis=read();
        add(from,to,dis);
        add(to,from,dis);
    }
    for(int i=1;i<=m;++i)    q[i]=(Node){read(),read(),0,0};
    find(1,1);
    for(int j=1;j<20;++j)
        for(int i=1;i<=n;++i){
            s[i][j]=s[s[i][j-1]][j-1];
            d[i][j]=d[i][j-1]+d[s[i][j-1]][j-1];
        }
    for(int i=1;i<=m;++i){
        int from=q[i].from,to=q[i].to;    int &dis=q[i].dis,&lca=q[i].lca;
        if(deep[from]<deep[to])    swap(from,to);
        int f=deep[from]-deep[to];
        for(int j=0;(1<<j)<=f;++j)
            if(f&(1<<j)){
                dis+=d[from][j];
                from=s[from][j];
            }
        if(from==to){
            lca=from;
            Max=max(Max,dis);
            continue;
        }
        for(int j=19;j>=0;--j){
            if(s[from][j]==s[to][j])    continue;
            dis+=d[from][j]+d[to][j];
            from=s[from][j];to=s[to][j];
        }
        dis+=d[from][0]+d[to][0];
        lca=s[from][0];
        Max=max(Max,dis);
    }
    sort(q+1,q+m+1);
    int l=0,r=Max;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){    ans=mid;r=mid-1;    }
        else        l=mid+1;
    }
    printf("%d",ans);
    return 0;
}