[NOIp 2015]运输计划

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

Sample Output

Sample Explanation

Hint

题解

抓取有用信息:

1、给定一棵$n$个点的带边权的树,给定$m$条路径;
2、求将任意一条边的边权置为$0$后所有路径长度最大值的最小值。

20分算法:

1、由于是一棵树,所以所有的路径都是最短路径,结合题目给定的数据范围,可以用合适的数据结构解决;
2、枚举被操作的边,$DFS$统计所有路径长度的最大值,然后更新答案;
3、时间复杂度$O(n^2*m)$。

40分算法:

1、枚举被操作的边,使用树链剖分等树上数据结构统计所有路径长度的最大值,然后更新答案;
2、时间复杂度$O(n^2log_2n)$。

60分算法:

1、先使用各种方法预处理出$LCA$,枚举被操作的边;
2、$DFS$在$O(n)$时间内统计所有路径的长度的最大值,然后更新答案;
3、时间复杂度$O(n^2)$。
如何用$DFS$在$O(n)$时间内统计所有路径的长度的最大值?
计算每一点到根的路径$dis[i]$,所以:
$$dist(u,v)=dis[u]+dis[v]-2*dis[LCA(u,v)]$$

100分算法:

1、先使用各种方法预处理出$LCA$与路径在未操作前的长度,推荐使用$Trajan$算法;
2、二分答案,即二分出路径长度的最大值$X$;
3、将所有长度大于$X$的路径找出来,求出最长的路径长度与$X$的差值$D$;
4、那么显然被删掉的边,边权$≥D$;然后使用各种方法求出这些路径的并集
(欧拉$DFS$序列或树上差分序列),看这些边的并集中是否有一条边的边权$≥D$,若有则该$X$可行。
5、时间复杂度$O(nlog_2n)$。

  1 #include<set>
  2 #include<map>
  3 #include<ctime>
  4 #include<cmath>
  5 #include<queue>
  6 #include<stack>
  7 #include<vector>
  8 #include<cstdio>
  9 #include<string>
 10 #include<cstring>
 11 #include<cstdlib>
 12 #include<iostream>
 13 #include<algorithm>
 14 #define LL long long
 15 #define Max(a,b) ((a)>(b) ? (a):(b))
 16 #define Min(a,b) ((a)<(b) ? (a):(b))
 17 using namespace std;
 18 const int N=300000;
 19 
 20 int n,m,u,v,c,lim;
 21 struct tt
 22 {
 23     int to,cost,next;
 24 }edge[N*2+5];
 25 int path[N+5],top;
 26 void Add(int u,int v,int c);
 27 struct ss
 28 {
 29     int a,b,lca,cost;
 30 }p[N+5];
 31 int fa[N+5][20],dist[N+5],dep[N+5];
 32 void Dfs(int r,int depth);
 33 void ST();
 34 void LCA(int k);
 35 
 36 int vis[N+5],cnt;
 37 bool work(int r);
 38 int judge(int r,int father);
 39 
 40 int main()
 41 {
 42     scanf("%d%d",&n,&m);
 43     lim=log(n)/log(2);
 44     for (int i=1;i<n;i++)
 45     {
 46   　　  scanf("%d%d%d",&u,&v,&c);
 47   　　  Add(u,v,c);
 48     　　Add(v,u,c);
 49     }
 50     for (int i=1;i<=m;i++) scanf("%d%d",&p[i].a,&p[i].b);
 51     Dfs(1,1);
 52     ST();
 53     int maxlenth=0;
 54     for (int i=1;i<=m;i++)
 55     {
 56    　　 LCA(i);
 57  　　   if (p[i].cost>maxlenth) maxlenth=p[i].cost;
 58     }
 59     int l=0,r=maxlenth,ans=maxlenth;
 60     while (l<=r)
 61     {
 62   　　  int mid=(l+r)>>1;
 63  　　   if (work(mid)) ans=mid,r=mid-1;
 64     　　else l=mid+1;
 65     }
 66     printf("%d
",ans);
 67     return 0;
 68 }
 69 
 70 void Add(int u,int v,int c)
 71 {
 72     edge[++top].to=v;
 73     edge[top].cost=c;
 74     edge[top].next=path[u];
 75     path[u]=top;
 76 }
 77 void Dfs(int r,int depth)
 78 {
 79     dep[r]=depth;
 80     for (int i=path[r];i;i=edge[i].next) if (!dep[edge[i].to])
 81     {
 82    　　 fa[edge[i].to][0]=r;
 83   　　  dist[edge[i].to]=dist[r]+edge[i].cost;
 84     　　Dfs(edge[i].to,depth+1);
 85     }
 86 }
 87 void ST()
 88 {
 89     for (int t=1;t<=lim;t++)
 90   　　  for (int i=1;i<=n;i++)
 91   　　      fa[i][t]=fa[fa[i][t-1]][t-1];
 92 }
 93 void LCA(int k)
 94 {
 95     int a=p[k].a,b=p[k].b;
 96     if (dep[a]<dep[b]) swap(a,b);
 97     for (int i=lim;i>=0;i--) if (dep[fa[a][i]]>=dep[b]) a=fa[a][i];
 98     if (a!=b)
 99     {
100   　　  for (int i=lim;i>=0;i--) if (fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];
101  　　   a=fa[a][0],b=fa[b][0];
102     }
103     p[k].lca=a;
104     p[k].cost=dist[p[k].a]+dist[p[k].b]-2*dist[p[k].lca];
105 }
106 bool work(int r)
107 {
108     memset(vis,0,sizeof(vis));
109     cnt=0;
110     int maxlenth=0;
111     for (int i=1;i<=m;i++)
112    　　 if (p[i].cost>r)
113   　　  {
114     　　    cnt++,maxlenth=Max(maxlenth,p[i].cost);
115       　　  vis[p[i].a]++,vis[p[i].b]++,vis[p[i].lca]-=2;
116     　　}
117     int delta=maxlenth-r;
118     maxlenth=judge(1,0);
119     return maxlenth>=delta;
120 }
121 int judge(int r,int father)
122 {
123     int ans=0;
124     for (int i=path[r];i;i=edge[i].next) if (edge[i].to!=father)
125     {
126   　　  int tmp=judge(edge[i].to,r);
127  　　   ans=Max(ans,tmp);
128    　　 vis[r]+=vis[edge[i].to];
129     }
130     if (vis[r]==cnt) ans=Max(ans,dist[r]-dist[fa[r][0]]);
131     return ans;
132 }