洛谷 P2680 运输计划-二分+树上差分(边权覆盖)

P2680 运输计划

题目背景

公元

题目描述

公元

L 国有

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

为了鼓励科技创新，

在虫洞的建设完成前小 P 的物流公司就预接了

如果小

输入输出格式

输入格式：

第一行包括两个正整数

接下来 $a_i, b_iai,bi 和 t_iti，表示第 ii 条双向航道修建在 a_iai 与 b_ibi 两个星球之间，任意飞船驶过它所花费的时间为 t_iti。数据保证 1 leq a_i,b_i leq n1≤ai,bi≤n 且 0 leq t_i leq 10000≤ti≤1000。$

接下来 $u_juj 和 v_jvj，表示第 jj 个运输计划是从 u_juj 号星球飞往 v_jvj号星球。数据保证 1 leq u_i,v_i leq n1≤ui,vi≤n$

输出格式：

一个整数，表示小

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

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

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

这道题有点东西。本来是想练手树上差分的，发现很多题解都是用二分+树链剖分写的，看了一下，树链剖分、线段树、树状数组(求线段标记次数)、LCA(有的是用tarjan求的路径的长度)。

一开始我看到这道题的时候，看到所有的计划都一起跑，就有点傻了，一起跑可怎么找，感觉直接暴力找回超时，后来算了一下，好像可以过。

我的思路就是：一开始的时候，先把所有的路径的长度出来，然后通过dfs把lca的相关东西处理出来，每一条线段的长度先保存一下，然后二分，最长的路径长度为右端点r，二分，每二分一次就遍历一下所有的路径，大于mid长度的，就树上差分保存一下，然后dfs一下就把所有的线段的标记次数找出来了，然后找一下是不是有某条线段被标记的次数为加入的路径的数量，如果有，就说明删掉这条边是可能成立的，最长的路径-这条线段与mid比较一下就可以了，有一点就是标记的次数相同的找最长的那条线段，一开始智障，找到了就跳出去了，wa了。。。

还有一点就是存边的时候数组开二倍，还有一点就是每一条线段的长度保存的时候，不能直接在输入的时候保存，这样会wa，因为用大的数当边的编号是对的，假设1和5相连，5和3相连，一开始1和5相连长度为3，输入的时候，我存的是vv[5]=3;但是等到我存5和3长度为5的时候，vv[5]=5,就不对了。soga，嘎嘎。

测评姬有点情绪不稳，相同的代码我第一次交有一个样例点tle，再交一次一模一样的，过了。。。试了好几次，网卡的时候就容易tle。。。

代码:

  1 //洛谷 P2680 运输计划 二分+树上差分(边覆盖)
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<cstdlib>
  8 using namespace std;
  9 typedef long long ll;
 10 const int maxn=3e5+10;
 11 
 12 struct node{
 13     int to,val,next;
 14 }edge[maxn<<1];
 15 
 16 int p1[maxn],p2[maxn],vv[maxn],maxx=0,ret,num,n,m,cnt,ans;
 17 int head[maxn<<1],sum[maxn],dep[maxn],fa[maxn][30],dis[maxn],len[maxn];
 18 
 19 void add(int x,int y,int v){edge[++cnt].to=y,edge[cnt].val=v,edge[cnt].next=head[x],head[x]=cnt;}
 20 
 21 void dfs(int u,int fath)
 22 {
 23     dep[u]=dep[fath]+1,fa[u][0]=fath;
 24     for(int i=0;fa[u][i];++i) fa[u][i+1]=fa[fa[u][i]][i];
 25     for(int i=head[u];i;i=edge[i].next){
 26         int v=edge[i].to,w=edge[i].val;
 27         if(v!=fath) dis[v]=dis[u]+w,vv[v]=w,dfs(v,u);//vv的dfs一开始写挫了，直接写到输入那里了
 28     }
 29 }
 30 
 31 int LCA(int u,int v)
 32 {
 33     if(dep[u]>dep[v]) swap(u,v);
 34     for(int i=21;i>=0;i--) if(dep[u]<=dep[v]-(1<<i)) v=fa[v][i];
 35     if(u==v) return u;
 36     for(int i=21;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
 37     return fa[u][0];
 38 }
 39 
 40 void Dfs(int u,int fath)//标记之后的Dfs
 41 {
 42     for(int i=head[u];i;i=edge[i].next){
 43         int v=edge[i].to;
 44         if(v==fath) continue;
 45         Dfs(v,u);
 46         sum[u]+=sum[v];
 47     }
 48     if(num==sum[u]){//如果标记的次数正好为加的边的数量，说明这一段在所有边上都有
 49         ret=max(ret,vv[u]);//标记次数相同的找长度最大的
 50     }
 51 }
 52 
 53 bool pig(int h)//判断
 54 {
 55     num=0;ret=0; memset(sum,0,sizeof(sum));
 56     for(int i=1;i<=m;i++){
 57         if(len[i]>h){
 58             num++;int lca=LCA(p1[i],p2[i]);
 59             sum[p1[i]]++;sum[p2[i]]++;sum[lca]-=2;
 60         }
 61     }
 62     if(!num) return 1;
 63     Dfs(1,0);return maxx-ret<=h;
 64 }
 65 
 66 int main()
 67 {
 68     scanf("%d%d",&n,&m);
 69     for(int i=1;i<n;i++){
 70         int u,v,w;
 71         scanf("%d%d%d",&u,&v,&w);
 72         add(u,v,w);add(v,u,w);//vv[max(u,v)]=w;
 73     }
 74     dfs(1,0);
 75     for(int i=1;i<=m;i++){
 76         int x,y;
 77         scanf("%d%d",&x,&y);
 78         p1[i]=min(x,y);p2[i]=max(x,y);
 79         int lca=LCA(x,y);
 80         len[i]=dis[x]+dis[y]-2*dis[lca];
 81         maxx=max(maxx,len[i]);
 82     }
 83     int l=0,r=maxx;
 84     while(l<=r){
 85         int mid=(l+r)>>1;//cout<<"mid= "<<mid<<endl;
 86         if(pig(mid))
 87             r=mid-1;
 88         else
 89             l=mid+1;
 90     }
 91     cout<<l<<endl;
 92 
 93 }
 94 /*
 95 6 3
 96 1 2 3
 97 1 6 4
 98 1 3 7
 99 3 4 6
100 3 5 5
101 3 6 
102 2 5 
103 4 5
104 
105 
106 11
107 
108 */

不开心，最近状态不好，铁了一年了。唉，菜是原罪。