题目背景

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

说明

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

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

---

这题首先用的是二分+暴力判断

二分答案然后把大于m的树链一一枚举，找可行的边取交集

80分

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #define MAXN 300005  6 #define LOG 20  7 #define pii pair
           
              8 using namespace std;  9 int first[MAXN],Next[MAXN*2],to[MAXN*2],W[MAXN*2],cnt; 10 int n,m; 11 int fa[LOG][MAXN],d[LOG][MAXN],dep[MAXN]; 12 int mid; 13 struct Lian{ 14     int x,y,lca; 15     int Val; 16     friend bool operator < (const Lian &p1,const Lian &p2){ 17         return (p1.Val
            
              (const Lian &p1,const Lian &p2){ 20 return !(p1.Val
             
              >=1,p++){ 46 if(k&1){ 47 L+=d[p][x]; 48 x=fa[p][x]; 49 } 50 } 51 if(x==y){ 52 return make_pair(L,x); 53 } 54 for(int k=LOG-1;k>=0;k--){ 55 if(fa[k][x]!=fa[k][y]){ 56 L+=d[k][x]; 57 L+=d[k][y]; 58 x=fa[k][x]; 59 y=fa[k][y]; 60 } 61 } 62 return make_pair(L+d[0][x]+d[0][y],fa[0][x]); 63 } 64 int b[MAXN]; 65 bool check(){ 66 memset(b,0,sizeof(b)); 67 Lian t;t.Val=mid; 68 int Pos=upper_bound(s+1,s+m+1,t)-s; 69 if(Pos>m){ 70 return 1; 71 } 72 int num=m-Pos+1; 73 for(int i=Pos;i<=m;i++){ 74 int lc=s[i].x,rc=s[i].y; 75 int lca=s[i].lca,L=s[i].Val; 76 while(lc!=lca){ 77 if(L-d[0][lc]<=mid){ 78 b[lc]++; 79 if(b[lc]>=num){ 80 return 1; 81 } 82 } 83 lc=fa[0][lc]; 84 } 85 while(rc!=lca){ 86 if(L-d[0][rc]<=mid){ 87 b[rc]++; 88 if(b[rc]>=num){ 89 return 1; 90 } 91 } 92 rc=fa[0][rc]; 93 } 94 } 95 return 0; 96 } 97 int main() 98 { 99 // freopen("T1.in","r",stdin);100 // freopen("my.out","w",stdout);101 scanf("%d%d",&n,&m);102 for(int i=1;i
             
            
           
          
         
        
       

实际上判断用树上差分提高效率即可AC

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #define MAXN 300005  6 #define LOG 20  7 #define pii pair
           
              8 using namespace std;  9 int first[MAXN],Next[MAXN*2],to[MAXN*2],W[MAXN*2],cnt; 10 int n,m; 11 int fa[LOG][MAXN],d[LOG][MAXN],dep[MAXN]; 12 int mid; 13 struct Lian{ 14     int x,y,lca; 15     int Val; 16     friend bool operator < (const Lian &p1,const Lian &p2){ 17         return (p1.Val
            
              (const Lian &p1,const Lian &p2){ 20 return !(p1.Val
             
              >=1,p++){ 46 if(k&1){ 47 L+=d[p][x]; 48 x=fa[p][x]; 49 } 50 } 51 if(x==y){ 52 return make_pair(L,x); 53 } 54 for(int k=LOG-1;k>=0;k--){ 55 if(fa[k][x]!=fa[k][y]){ 56 L+=d[k][x]; 57 L+=d[k][y]; 58 x=fa[k][x]; 59 y=fa[k][y]; 60 } 61 } 62 return make_pair(L+d[0][x]+d[0][y],fa[0][x]); 63 } 64 int b[MAXN]; 65 int num; 66 int find(int x){ 67 int ret=0; 68 for(int e=first[x];e;e=Next[e]){ 69 int y=to[e]; 70 if(y==fa[0][x]) continue; 71 ret=max(ret,find(y)); 72 b[x]+=b[y]; 73 } 74 if(b[x]==num){ 75 ret=max(ret,d[0][x]); 76 } 77 return ret; 78 } 79 bool check(){ 80 memset(b,0,sizeof(b)); 81 Lian t;t.Val=mid; 82 int Pos=upper_bound(s+1,s+m+1,t)-s; 83 if(Pos>m){ 84 return 1; 85 } 86 num=m-Pos+1; 87 for(int i=Pos;i<=m;i++){ 88 int lc=s[i].x,rc=s[i].y; 89 int lca=s[i].lca,L=s[i].Val; 90 b[lc]++,b[rc]++; 91 b[lca]-=2; 92 } 93 int temp=find(1); 94 return (s[m].Val-temp<=mid); 95 } 96 int main() 97 { 98 // freopen("T1.in","r",stdin); 99 // freopen("my.out","w",stdout);100 scanf("%d%d",&n,&m);101 for(int i=1;i