[noip2015]運輸計劃——倍增

題目背景

公元 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

說明

請注意常數因子帶來的程式效率上的影響。

首先注意到每一條航線的最短路徑即為兩點各自到達LCA的距離之和，是以為了處理每一條航線的最初長度，即可以采用倍增的做法來處理，由于若幹條的航班是同時開始的，是以題意就是求在把一條邊的邊權變為零了之後的最大航線路程的最小值，是以可以采用二分答案法來枚舉

有關于在枚舉了答案之後如何進行答案的判斷，我們可以枚舉每一條航線，然後尋找時間大于mid的航線，對于每一條邊對該航線做出的貢獻進行統計，如果沒有一條邊使得該航線的時間符合要求，則可以return 0；但是還要記錄每一條邊在航線中出現的次數，最後判斷如有一條邊出現的次數等于不符合要求的航線個數并且做出的貢獻是符合要求的，就可以return 1了，否則還是return 0；

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
#define Mid ((l+r)/2)
using namespace std;
const int maxn=+;
inline void read(int &x){
    int sum=;
    char c=getchar();
    while(c<'0' || c>'9')c=getchar();
    while(c>='0' && c<='9'){
        sum=(sum<<)+(sum<<)+(c^'0');
        c=getchar();
    }
    x=sum;
}
int n,m,beg[maxn],len;
int maxdep,dep[maxn],lca[maxn][],lcw[maxn][];//maxdep為最大深度，lca為倍增數組，lcw為到第2^j祖先的路徑的長度總和
int x[maxn],y[maxn],an[maxn],cost[maxn];//x,y為航線的兩點，an為祖先，cost為原本的時間
int l,r;
bool vis[maxn];
struct egde{
    int to;
    int last;
    int w;
}E[maxn*];
inline void add(int u,int v,int w){
    ++len;
    E[len].to=v;
    E[len].last=beg[u];
    E[len].w=w;
    beg[u]=len;
}
inline void dfs(int u,int deep){//dfs初始化dep和maxdep
    if(deep>maxdep)maxdep=deep;
    dep[u]=deep;
    vis[u]=;
    for(register int i=beg[u];i;i=E[i].last){
        int v=E[i].to;
        if(vis[v])continue;
        lca[v][]=u;
        lcw[v][]=E[i].w;
        dfs(v,deep+);
    }
}
inline void cal(){//處理倍增數組
    for(register int i=;(<<i)<=maxdep;++i)
        for(register int j=;j<=n;++j)
            if(dep[j]-(<<i)>=)
                lca[j][i]=lca[lca[j][i-]][i-];
    for(register int i=;(<<i)<=maxdep;++i)
        for(register int j=;j<=n;++j)
            if(dep[j]-(<<i)>=)
                lcw[j][i]=lcw[j][i-]+lcw[lca[j][i-]][i-];
}
inline void work(int a,int b,int i){//倍增
    int sum=,ans=;
    if(dep[a]<dep[b])swap(a,b);
    while(dep[a]>dep[b]){
        int k=;
        while(dep[lca[a][k+]]>=dep[b])++k;
        sum+=lcw[a][k];a=lca[a][k];
    }
    while(a!=b){
        int k=;
        while(lca[a][k+]!=lca[b][k+])++k;
        sum+=lcw[a][k];sum+=lcw[b][k];
        a=lca[a][k];b=lca[b][k];
    }
    an[i]=a;
    cost[i]=sum;
}
inline bool check(int mid){//判斷答案
    int have[maxn]={},cnt[maxn]={},CNT=;
    for(register int i=;i<=m;++i)
        if(cost[i]>mid){
            ++CNT;
            int a=x[i],b=y[i],Min=;
            for(register int j=a;j!=an[i];j=lca[j][]){
                if(cost[i]-lcw[j][]>have[j])
                    have[j]=cost[i]-lcw[j][];
                if(have[j]<Min)
                    Min=have[j];
                ++cnt[j];
            }
            for(register int j=b;j!=an[i];j=lca[j][]){
                if(cost[i]-lcw[j][]>have[j])
                    have[j]=cost[i]-lcw[j][];
                if(have[j]<Min)
                    Min=have[j];
                ++cnt[j];
            }
            if(Min>mid)return false;
        }
    for(register int i=;i<=n;++i)
        if(have[i]<=mid && cnt[i]==CNT)
            return true;
    return false;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("plan.in","r",stdin);
    freopen("plan.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    for(register int i=;i<=n-;++i){
        int u,v,w;
        read(u);read(v);read(w);
        add(u,v,w);add(v,u,w);
    }
    for(register int i=;i<=m;++i)
        read(x[i]),read(y[i]);
    dfs(,);
    cal();
    for(register int i=;i<=m;++i){
        work(x[i],y[i],i);
        if(cost[i]>r)
        r=cost[i];
    }
    while(l+<r){//二分答案啦
        if(check(Mid))r=Mid;
        else l=Mid+;
    }
    if(check(l))printf("%d\n",l);
    else printf("%d\n",r);
    return ;
}