运输计划（倍增95pts）

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 300005

int n,m,cnt,maxi,ans,cha[MAXN],tot[MAXN],beyond,longest,
    head[MAXN],fa[MAXN][25],dep[MAXN],dis[MAXN],tofa[MAXN];

struct edge{
    int v,w,next;
}e[MAXN<<1];

inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

struct node{
    int u,v,lca,dis;
}s[MAXN];

inline bool cmp(node x,node y){
    return x.dis>y.dis;
}

inline void deal_first(int u,int fau){
//  printf("%d %d\n",u,fau);
    dep[u]=dep[fau]+1;
    fa[u][0]=fau;
    for(int i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i!=-1;i=e[i].next){
        if(e[i].v==fau)continue;
        tofa[e[i].v]=e[i].w;
        dis[e[i].v]=dis[u]+e[i].w;
        deal_first(e[i].v,u);
    }
}

inline int lca(int x,int y){
    if(dep[x]<dep[y])std::swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[x]-dep[y]>=(1<<i))x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

inline int getdfs(int u){
    tot[u]=cha[u];
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(v==fa[u][0])continue;
        tot[u]+=getdfs(v);
    }
    if(tot[u]==beyond)longest=std::max(longest,tofa[u]);
    return tot[u];
}

inline bool check(int x){
    beyond=longest=0;
    memset(cha,0,sizeof(cha));
    memset(tot,0,sizeof(tot));
    for(int i=1;i<=m;i++){
        if(s[i].dis<=x)break;
        beyond++;
        cha[s[i].u]++;
        cha[s[i].v]++;
        cha[s[i].lca]-=2;
    }
    getdfs(1);
    if(s[1].dis-longest<=x)return true;
    return false;
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++){
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        add(a,b,t);
        add(b,a,t);
    }
//  printf("alive\n");
    deal_first(1,0);
//  printf("alive\n");
    for(int i=1;i<=m;i++){
        scanf("%d%d",&s[i].u,&s[i].v);
        s[i].lca=lca(s[i].u,s[i].v);
        s[i].dis=dis[s[i].u]+dis[s[i].v]-2*dis[s[i].lca];
        maxi=std::max(maxi,s[i].dis);
    }
//  printf("alive\n");
    std::sort(s+1,s+m+1,cmp);
    int l=0,r=maxi;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
//  printf("alive\n");
    printf("%d\n",ans);
}

又出现这个错误：head没memset见祖宗

运输计划（倍增95pts）

原文：https://www.cnblogs.com/Y15BeTa/p/11722161.html