题目描述
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的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5
11
说明
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
自测考场上因为时间被T1卡了时间，结果代码出了偏差，只剩下5分.....
首先，先用倍增处理出每个任务的耗时，将所有的任务按耗时排序。然后二分，假设删除一条边后所有任务中最大耗时≤mid，随后在不删除任何边的条件下找出这n个任务中耗时＞mid的所有任务，若要使这些任务的耗时降低至mid同时使最终答案尽可能地小，则所删除的那条边必满足其同时在这些任务的路径中且最长。若不存在符合条件的边或(最长耗时-符合条件最长边长度)>mid 则l=mid+1,否则r=mid，最终输出l即可。
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define M 310000 7 using namespace std; 8 struct edge{int u,v,next;}e[M*2]={0}; int use=0,head[M]={0}; 9 void add(int x,int y,int z){use++;e[use].u=y; e[use].v=z; e[use].next=head[x]; head[x]=use;} 10 int dep[M]={0},dis[M][20]={0},f[M][20]={0}; 11 12 void dfs(int x,int fa,int v){ 13 dep[x]=dep[fa]+1; dis[x][0]=v; f[x][0]=fa; 14 for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1],dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1]; 15 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa) dfs(e[i].u,x,e[i].v); 16 } 17 int getlca(int x,int y){ 18 if(dep[x]<dep[y]) swap(x,y); int cha=(dep[x]-dep[y]); 19 for(int i=19;i>=0;i--) if((1<<i)&cha) x=f[x][i]; 20 for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; 21 if(x!=y) return f[x][0]; return x; 22 } 23 int getdis(int x,int y){ 24 int lca=getlca(x,y),ans=0; 25 int cha=dep[x]-dep[lca]; 26 for(int i=19;i>=0;i--) if((1<<i)&cha) ans+=dis[x][i],x=f[x][i]; 27 cha=dep[y]-dep[lca]; 28 for(int i=19;i>=0;i--) if((1<<i)&cha) ans+=dis[y][i],y=f[y][i]; 29 return ans; 30 } 31 struct ask{ 32 int x,y,lca,dis; ask(){x=y=dis=0;} 33 ask(int xx,int yy){x=xx; y=yy; lca=getlca(x,y); dis=getdis(x,y);} 34 friend bool operator <(ask a,ask b){return a.dis<b.dis;} 35 }p[M]; 36 int tag[M]={0},smp=0,maxn=0; 37 int dfs(int x,int fa){ 38 int sum=0; 39 for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){ 40 int cnt=dfs(e[i].u,x); 41 if(cnt==smp) maxn=max(maxn,e[i].v); 42 sum+=cnt; 43 } 44 return sum+tag[x]; 45 } 46 47 int main(){ 48 //freopen("transport.in","r",stdin); 49 //freopen("transport.out","w",stdout); 50 int n,m; scanf("%d%d",&n,&m); 51 for(int i=1;i<n;i++){ 52 int x,y,z; scanf("%d%d%d",&x,&y,&z); 53 add(x,y,z); add(y,x,z); 54 } 55 dfs(1,0,0); 56 for(int i=1;i<=m;i++){ 57 int x,y; scanf("%d%d",&x,&y); 58 p[i]=ask(x,y); 59 } 60 sort(p+1,p+m+1); 61 int l=0,r=1e9; 62 while(l<r){ 63 int mid=(l+r)>>1; smp=maxn=0; 64 ask op; op.dis=mid; 65 int k=upper_bound(p+1,p+m+1,op)-p;// k--; 66 smp=m-k+1; 67 if(smp==0){r=mid; continue;} 68 for(int i=k;i<=m;i++){ 69 tag[p[i].x]++; tag[p[i].y]++; 70 tag[p[i].lca]-=2; 71 } 72 dfs(1,0); 73 for(int i=k;i<=m;i++){ 74 tag[p[i].x]--; tag[p[i].y]--; 75 tag[p[i].lca]+=2; 76 } 77 if(p[m].dis-maxn<=mid) r=mid; 78 else l=mid+1; 79 } 80 cout<<l<<endl; 81 }