「NOIP 2015」运输计划

发表于 | | 阅读次数:
字数统计: 939 字

Description

题目链接：Luogu 2680

L 国有 $n$ 个星球，有 $n-1$ 条双向航道连通了 L 国的所有星球，每条航道连通两个星球，第 $i$ 条航道通过的时间为 $t_i$。

小 P 掌管的物流公司有 $m$ 个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的路径到 $v_i$ 号星球去。注意：任意两艘飞船之间不会产生任何干扰。

在运输计划开始前，小 P 可以自由选择一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。求出小 P 的物流公司完成阶段性工作所需要的最短时间。

数据范围：$n,m\le 3\times 10^5$，$0\le t_i\le 1000$

Solution

我们首先注意到最终的答案为：所有运输计划的最大值。而我们要最小化答案，所以可以先二分答案。

设每条链的长度为 $len_i$，现在二分得到的答案为 $x$。如果第 $i$ 条链的长度 $len_i>x$，那么意味选择修改的边必须要在第 $i$ 条链上。我们统计出需要修改的链的数量 $cnt$，并把这些链上的所有边打上标记，这个过程可以使用树上差分（对于边差分）或者树链剖分（复杂度多一个 $\log$）实现。当一条边被标记的次数等于 $cnt$ 并且它的长度 $\geqslant\text{最长的链的长度}-x$ 时，这个 $x$ 为合法的，因为我们可以修改这条边，使得最长的链的长度减小到 $\le x$；否则 $x$ 这个答案不合法。

时间复杂度：$O(n\log n)$

Code

一个小技巧：树上差分最后可以使用 $\text{DFS}$ 序进行前缀和计算。

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=3e5+5,M=1e6+5;
int n,m,tot,idx,lnk[N],ter[M],nxt[M],val[M],up[N],dep[N],dis[N],seq[N];
int mx,s[N],t[N],p[N],len[N],f[N][21],d[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void dfs(int u,int fa) {
    seq[++idx]=u,f[u][0]=fa,dep[u]=dep[fa]+1;
    for(int i=1;(1<<i)<=dep[u];++i) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==fa) continue;
        dis[v]=dis[u]+val[i],up[v]=val[i];
        dfs(v,u);
    }
}
int LCA(int x,int y) {
    if(dep[x]>dep[y]) x^=y^=x^=y;
    for(int i=20;~i;--i) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
    if(x==y) return x;
    for(int i=20;~i;--i) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
bool check(int x) {
    memset(d,0,sizeof(d));
    int cnt=0;
    for(int i=1;i<=m;++i) {
        if(len[i]>x) ++d[s[i]],++d[t[i]],d[p[i]]-=2,++cnt;
    }
    for(int i=n;i>=1;--i) {
        int k=seq[i];
        d[f[k][0]]+=d[k];
        if(d[k]==cnt&&up[k]>=mx-x) return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    dfs(1,0);
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&s[i],&t[i]);
        p[i]=LCA(s[i],t[i]);
        len[i]=dis[s[i]]+dis[t[i]]-2*dis[p[i]];
        mx=std::max(mx,len[i]);
    }
    int l=0,r=mx,ans;
    while(l<=r) {
        int mid=1LL*(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}
0%