NOIP2015 运输计划树上差分+树剖

悠悠 2023-06-04 08:00 22阅读 0赞

[**题目链接**][Link 1]

**震惊noip被ccf暂停了，不过多半是改个名字什么的。noip的好题还是可以做一做的，这道题的确值得一做，我们看他题上说的是最短的时间是所有经过边权和的最大值决定，也就是说最大值最小，显然的二分答案。由于题目中的关系是一棵树或一条链，所以就可以往这方面想想，可是我就想不到。先打个暴力三十分，针对那些m等于1的情况，直接求出两点间的最短路再减去最短路径上的最长边就可以了。spfa复杂度O（玄学），堆优化dijkstra是O（nlogn），30分就到手了。不过要打正解还是挺不容易的，还是去看看题解是怎么说的，大多数的题解都提到了树上差分这个玩意儿。那我们还是考虑一下，先用树剖求LCA，预处理出询问的点两两之间的距离，然后二分check+树上差分，check就check最大值最小。**

**关键步骤便是这个树上差分，推荐[此博客][Link 2]**

**我们一旦发现一个路径大于我们的答案，就把该路径的两个端点记录下来有多少次经过，也就是树上差分。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

cha[q[i].fro]++;
    cha[q[i].to]++;
    cha[q[i].lca]-=2;

**短短几行但是非常有用，然后我们再求出该答案与超出的那个边权的差的最大值。之后更新所有点的差分数组，因为树上两点间路径唯一，所以要想从某个点过，必须先从它father身上过。所以他的差分值累加到father上。**

**最后便是判断，如果有某个点被经过的次数恰好是不合法边的数量，边权比最大差值大或等于，就是一个可行解，就将该点的边改为虫洞即可。**

**还要记住每次二分答案的时候，差分数组要清空，从头再来。最终复杂度O（nlogn）。**

**完整的代码如下**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+7;
    int dep[maxn],son[maxn],size[maxn],w[maxn],fa[maxn],dis[maxn],hash[maxn];
    int top[maxn],id[maxn],rev[maxn],Time;
    int cha[maxn];
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    struct node1{
        int fro,to,lca,diss;
    }q[maxn*4];
    int head[maxn],cnt;
    int n,m,x,y,v,qx,qy;
    int sum,l,r;
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    void dfs1(int x,int f){
        fa[x]=f;
        dep[x]=dep[f]+1;
        size[x]=1;
        int maxson=-1;
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==fa[x]) continue;
            dis[go]=dis[x]+edge[i].val;
            dfs1(go,x);
            size[x]+=size[go];
            if(size[go]>maxson){
                maxson=size[go];
                son[x]=go;
            }
        }
    }
    void dfs2(int x,int topf){
        top[x]=topf;
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==son[x]||go==fa[x]) continue;
            dfs2(go,go); 
        }
    }
    int LCA(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            x=fa[top[x]];
        } 
        return dep[x]<dep[y]?x:y;
    }
    //--------------------------------以上是树剖求LCA部分 
    void dfs3(int x){
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==fa[x]) continue;
            dfs3(go);
            cha[x]+=cha[go];
        }
    }
    void dfs4(int x){
        for(int i=head[x];i;i=edge[i].nxt){
            int go=edge[i].to;
            if(go==fa[x]) continue;
            hash[go]=i;//记录下出边的序号 
            dfs4(go);
        }
    }
    bool check(int x){
        int cnt=0,ans=0;
        memset(cha,0,sizeof(cha));
        for(int i=1;i<=m;i++){
            if(q[i].diss>x){
         //如果有一条路径不符合 
                cha[q[i].fro]++;//记录下，相当于是树上差分每点权值+1 
                cha[q[i].to]++;
                cha[q[i].lca]-=2;
                cnt++;
                ans=max(ans,q[i].diss-x);
                //看最大的修改值  
            }
        }
        if(!cnt) return true;//没有不合法边，此答案可行 
        dfs3(1);//统计各点的差分次数  
        for(int i=1;i<=n;i++) if(cha[i]==cnt&&edge[hash[i]].val>=ans) return true;
        //如果有某个点是多个边的公共点，边权比最大差值大或等于，就是一个可行解 
        return false;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&x,&y,&v);
            add(x,y,v);add(y,x,v);
        }
        dfs1(1,0);dfs2(1,1);dfs4(1);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&qx,&qy);
            q[i].fro=qx;
            q[i].to=qy;
            q[i].lca=LCA(q[i].fro,q[i].to);
            q[i].diss=dis[q[i].fro]+dis[q[i].to]-2*dis[q[i].lca];//预处理出两点间路径 
            sum=max(sum,q[i].diss);
        }
        int ljb;
        l=0,r=sum;
        while(l<=r){
         //求最大值最小 
            int mid=(l+r)/2;
            if(check(mid)){
                ljb=mid;
                r=mid-1; 
            }
            else l=mid+1;
        }
        printf("%d\n",ljb);
        return 0;
    }

**好题。**

转载于:https://www.cnblogs.com/LJB666/p/11367918.html

[Link 1]: https://www.luogu.org/problem/P2680
[Link 2]: https://www.cnblogs.com/cjoierljl/p/8728215.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9eb3cea93d864ec6afab70094ecdf38d.png