Submit: 1460 Solved: 908
[Submit][Status][Discuss]
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。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n
Output
输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
Sample Input
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
Sample Output
HINT
Solution
首先我们考虑若答案为ans，则我们可以发现若一条航道的耗时大于ans，则一定在这条航道上有一条路径改造成了虫洞。若有多条航道耗时大于ans则这些航道的路径交中一定有一条改造成了虫洞，当然不难发现，选择路径交中耗时最多的一条路径改造成虫洞即路径长变为0是最优的。
我们又发现若答案ans是具有二分性的，则我们可以二分这个答案。
那我们如何来快速求路径交呢，我们可以用树上差分。对于x-y这套航道，即我们可以在lca(x,y)这个点处-2（记为f数组），x和y处+1，然后dfs遍历每个点，我们将每条边经过的此处转到节点上，即从u->v遍历，则将e(u-v)这条边的信息记录到v中（为什么要记录到后访问的点呢，因为遍历时对于每个点有多个儿子但只有一个父亲），而这条边被经过的次数也就是以v为根的子树中所有点的f[i]值的和。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long using namespace std; const int N=310000; int n,m,tot,Next[N*2],head[N],tree[N*2],dep[N],fa[N][20],X[N],Y[N],LCA[N]; int p[N],f[N],num[N],A[N]; ll val[N*2],sum[N],Sum[N],B[N]; bool visit[N]; void add(int x,int y,ll z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void dfs(int x,int depth,int father,ll s) { dep[x]=depth;sum[x]=s;fa[x][0]=father; for (int i=head[x];i;i=Next[i]) if (!dep[tree[i]]) dfs(tree[i],depth+1,x,s+val[i]); } int lca(int x,int y) { if (dep[x]>dep[y]) swap(x,y); int z=dep[y]-dep[x]; for (int i=19;i>=0;i--) { if (z<=0) break; if (1<<i<=z) z-=1<<i,y=fa[y][i]; } if (x==y) return x; for (int i=19;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void Dfs(int u) { num[u]=f[u]; visit[u]=true; for (int i=head[u];i;i=Next[i]) if (!visit[tree[i]]) { int v=tree[i]; Dfs(v); A[v]=num[v]; B[v]=val[i]; num[u]+=num[v]; } } bool check(ll x) { for (int i=1;i<=m;i++) p[i]=0; for (int i=1;i<=n;i++) f[i]=0,num[i]=-1,visit[i]=false; ll Max=0,ans=0; for (int i=1;i<=m;i++) if (Sum[i]>x) { p[i]=1; Max=max(Max,Sum[i]); } int t=0; for (int i=1;i<=m;i++) if (p[i]) { f[X[i]]++;f[Y[i]]++;f[LCA[i]]-=2; t++; } Dfs(1); for (int i=2;i<=n;i++) if (A[i]==t) ans=max(ans,B[i]); if (Max-ans>x) return false; return true; } ll erfen(ll l,ll r) { if (l>=r) return r; ll mid=(l+r)/2; bool flag=check(mid); if (flag) return erfen(l,mid);else erfen(mid+1,r); } int main() { scanf("%d%d",&n,&m); tot=0; long long MAX=0; for (int i=1;i<=n-1;i++) { int x,y;ll z; scanf("%d%d%lld",&x,&y,&z); add(x,y,z);add(y,x,z); } dfs(1,1,0,0); for (int i=1;i<=19;i++) for (int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; for (int i=1;i<=m;i++) { scanf("%d%d",&X[i],&Y[i]); LCA[i]=lca(X[i],Y[i]); Sum[i]=sum[X[i]]+sum[Y[i]]-2*sum[LCA[i]]; MAX=max(MAX,Sum[i]); } printf("%lld\n",erfen(0,MAX)); return 0; } |
