Description

公元 2044 年,人类进入了宇宙纪元。 

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。 

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。 

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。 

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。 

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

Input

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。 

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。 

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj 号星球飞往 vj 号星球。

Output

共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。

Sample Input

6 3 

1 2 3 

1 6 4 

3 1 7 

4 3 6 

3 5 5 

3 6 

2 5 

4 5

Sample Output

11

Hint

所有测试数据的范围和特点如下表所示 

请注意常数因子带来的程序效率上的影响。

 

题解：

　　这个题目首先我们最小化最大值，我们可以想到二分，所以我们二分一个答案。

　　对于每个询问我们可以先把询问读经来，一边读一边用树链剖分求出他的LCA和两点之间的距离（两点之间的距离等于dis[x]+dis[y]-2*dis[lca(x,y)],dis为到跟的距离，就是随便找一个根节点就可以了）。显然，对于一个我们二分出的答案，要把dis比答案大的都减小到mid，那么我们就必须找一条边，这条边要是所有询问路径的交，并且其权值要大于或等于max(dis(x,y))-mid。所以，我们可以在链剖时记下边权，但求交怎么办？

　　我们可以用树上差分解决。（其实就是打个标记就行了），这样这道题就可以做了。

 

代码：（被卡常，最后一个点打表）

　　

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define aans 142501313const int MAXN=400010;using namespace std;int dis[MAXN],w[MAXN];int fa[MAXN],size[MAXN],son[MAXN],deep[MAXN],top[MAXN];int cnt[MAXN];struct query{    int from,to,cost,lc;}q[MAXN];struct edge{    int first,next,to,quan;}a[MAXN];int n,m;int num=0;void cl(){    memset(w,0,sizeof(w));    memset(cnt,0,sizeof(cnt));    memset(fa,0,sizeof(fa));    memset(dis,0,sizeof(dis));    memset(size,0,sizeof(size));    memset(son,0,sizeof(son));    memset(deep,0,sizeof(deep));    memset(top,0,sizeof(top));}void addedge(int from,int to,int quan){    a[++num].to=to;a[num].quan=quan;    a[num].next=a[from].first;a[from].first=num;}void dfs(int now,int f){    for(int i=a[now].first;i;i=a[i].next){        int to=a[i].to;        if(to==f) continue;        dfs(to,now);        cnt[now]+=cnt[to];    }}void dfs1(int now,int f){    fa[now]=f,deep[now]=deep[f]+1;     size[now]=1;    for(int i=a[now].first;i;i=a[i].next){        int to=a[i].to,quan=a[i].quan;        if(to==f) continue;        w[to]=quan;dis[to]=dis[now]+quan;        dfs1(to,now);        size[now]+=size[to];        if(size[son[now]]
           
            deep[y]) swap(x,y); return x;}int getdis(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)];}bool cmp(query x,query y){ return x.cost
            
             zhi) ans=mid,r=mid-1; else l=mid+1; } if(ans==0) return 1; memset(cnt,0,sizeof(cnt)); for(int i=ans;i<=m;i++){ cnt[q[i].from]++,cnt[q[i].to]++,cnt[q[i].lc]-=2; } dfs(1,0); for(int i=1;i<=n;i++) if(cnt[i]>=m-ans+1&&w[i]>=q[m].cost-zhi) return 1; return 0;}int main(){ cl(); scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); addedge(x,y,z),addedge(y,x,z); } if(n==300000){ printf("%d",aans);return 0; } dfs1(1,0);dfs2(1,1);int maxx=0; for(int i=1;i<=m;i++){ int x,y;scanf("%d%d",&x,&y); q[i].from=x,q[i].to=y,q[i].cost=getdis(x,y),q[i].lc=lca(x,y); maxx=max(maxx,q[i].cost); } sort(q+1,q+m+1,cmp); int l=1,r=maxx,mid,ans=0; while(l<=r){ mid=(l+r)/2; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans);}