cogs 2109. [NOIP 2015] 运输计划提高组Day2T3 树链剖分求LCA 二分答案差分

2109. [NOIP 2015] 运输计划

★★★☆ 输入文件：transport.in 输出文件：transport.out 简单对比
时间限制：3 s 内存限制：256 MB

【题目描述】

公元

L 国有

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从

为了鼓励科技创新，L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

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

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

【输入格式】

第一行包括两个正整数

接下来

【输出格式】

共

【样例输入】

【样例输出】

【提示】

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

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

【来源】

NOIP 2015 Day 2 Task 3

我的天呐我居然开始做提高组D2T3的题了！（不敢相信）

那么这一道题的正解是树链剖分LCA +差分 +二分答案 <<听起来好麻烦的样子啊

我们先来想一个暴力（60分）的做法吧

就是首先怎么想到树链剖分求LCA的呢很简单（今天刚学的啊）

就是题目不是要求出两个点之间的路径以及距离吗

LCA就可以实现啊

就是比如有一个dis数组（可以看我的上一篇题解）

那么dis[a]+dis[b]-dis[lca(a,b)]就是a 和 b之间的距离啊！！

然后就是枚举一下删掉那一条边呵呵肯定超时不是正解我就不再赘述了啊

满分做法看起来非常玄学

树链剖分LCA +差分+二分答案

二分答案的就是。。。就是答案啊就是最短的时间

首先肯定答案是满足可二分性的。。。（自己去想想吧）

然后首先求LCA 的部分就自己看代码吧

主要来讲一下怎样优化AC

首先第一个问题二分答案怎么检验

一个很简单的想法就是枚举每一条边很显然这和刚才的那个暴力的做法有什么区别呢（还更慢了）

首先有这么一个神奇的想法就是我们不用枚举每一条边了我们先在一开始的时候记录一个max_dis 嗯嗯嗯呃那肯定啊题目就是让求删掉一条边后最长的路径啊

嗯嗯就是我们可以枚举一下每一条呗多少的路径经过然后呢？？‘’

对于原长度大于mid的路径假设有cnt条其中最长的的一条长度设为max_dis

那么删去那条边必须被这cnt天路径经过

且这条边假设长度为dis 那么要有max_dis-dis<=mid

可以用差分数组来记录一下每条边有多少路径经过（不明白的可以看一看我的另一篇差分详解哦）

#include<vector>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define maxn 300005
//#define to e[i].to
using namespace std;
int n,m;
int dis[maxn],a[maxn],size[maxn],top[maxn],son[maxn],dfn[maxn],pos[maxn],Dp[maxn],fa[maxn],mark[maxn],cnt;
struct edge{
    int to;
    int val;
};
vector<edge> e[maxn];
int q[maxn][3],max_dis=0;
void addedge(int x,int y,int z){
    edge tmp;tmp.to=y;tmp.val=z;
    e[x].push_back(tmp);
    tmp.to=x;e[y].push_back(tmp);
}
void Dfs(int rt){
    size[rt]=1;
    for(int i=0;i<e[rt].size();i++){
        int to=e[rt][i].to;
        if(!size[to]){
            dis[to]=dis[rt]+e[rt][i].val;
            Dp[to]=Dp[rt]+1;
            fa[to]=rt;a[to]=e[rt][i].val;
            Dfs(to);
            size[rt]+=size[to];
            if(size[to]>size[son[rt]]) son[rt]=to;
        }
    }
}
void Dfs(int rt,int tp){
    top[rt]=tp;dfn[++cnt]=rt;pos[rt]=cnt;
    if(son[rt])     Dfs(son[rt],tp);
    for(int i=0;i<e[rt].size();i++){
        int to=e[rt][i].to;
        if(!top[to]) Dfs(to,to);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(Dp[top[x]]<Dp[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(Dp[x]>Dp[y]) swap(x,y);
    return x;
}
void beMark(int x,int y){
    int s=pos[x],t=pos[y];
    mark[s]++;mark[t+1]--;
}
void Mark(int x,int y){
    while(top[x]!=top[y]){
        if(Dp[top[x]]<Dp[top[y]]) swap(x,y);
        beMark(top[x],x);
        x=fa[top[x]];
    }
    if(Dp[x]>Dp[y]) swap(x,y);
    if(x!=y) beMark(son[x],y);
}
bool Check(int mid){
    int tot=0;
    memset(mark,0,sizeof(mark));
    for(int i=0;i<m;i++)
         if(q[i][2]>mid) tot++,Mark(q[i][0],q[i][1]);
    if(!tot) return true;
    for(int i=2;i<=n;i++) mark[i]+=mark[i-1];
    for(int i=2;i<=n;i++) if(mark[pos[i]]==tot&&max_dis-a[i]<=mid) return true;
    return false;
}
int main()
{
//    freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    Dfs(1);Dfs(1,1);
    for(int i=0;i<m;i++){
        int x,y;scanf("%d%d",&x,&y);
        q[i][0]=x;q[i][1]=y;q[i][2]=dis[x]+dis[y]-2*dis[lca(x,y)];
        max_dis=max(max_dis,q[i][2]);
    }
    int l=0,r=max_dis,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(Check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}

666

cogs 2109. [NOIP 2015] 运输计划 提高组Day2T3 树链剖分求LCA 二分答案 差分