【UOJ150】【NOIP2015】运输计划

Author Avatar
q234rty 7月 22, 2016

二分答案+树上差分即可。

考虑到答案是所有任务所用时间的最大值，因此二分答案。

这样原问题就变成了一个判定性的问题：是否可以在给定时间内完成所有任务。

先预处理出所有方案两个点的lca，以及dfs序。

对于每个答案，显然改造成虫洞的边一是所有所用时间大于答案的任务对应的链的交上的边中边权最大的一条。

于是我们求出链的交，选择边权最大的一条边，判断所用时间最长的任务的时间减去最大边权后是否不大于答案即可。

那么如何求链交？注意到如果我们把一条链上的所有边对应的值都加上 1 ,最后对应的值恰好等于链的个数的边一定是链交的一部分。我们定义对于每个点 i ,其到根的路径上的所有边的值都要加上 mark[i] 。对于每条链，我们只要使其两端的点的 mark 值 +1 ,其两端点的lca的 mark 值 -2 就可以啦。

对于每个点 i ,我们定义 val[i] 为其子树中所有点的 mark 值之和不难发现这也是其到它父亲的边对应的值。

这样，只要按照dfs序从后往前扫，对于每个点 i 把 val[i] 加上 mark[i] ,并把 val[fa[i]] 加上 val[i] 。如果 val[i] 等于链的个数，说明点 i 到其父亲的边是链交的一部分，更新最大值即可。

我使用了树链剖分求lca，时间复杂度 O(n\log{1000n}) 。

Code

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXSIZE=10000020;
const int INF=0x3f3f3f3f;
int bufpos;
char buf[MAXSIZE];
void init(){
    #ifdef LOCAL
        freopen("4326.txt","r",stdin);
    #endif // LOCAL
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
const int maxn=300001;
const int maxq=300001;
const int maxm=600001;
struct query{
    int u,v,lc,len;
    bool operator < (const query& rhs)const{
        return len>rhs.len;
    }
};
struct edge{
    int to,cost,next;
};
struct graph{
    int n,m;
    edge e[maxm];
    int first[maxn];
    int dep[maxn],fa[maxn],top[maxn],sz[maxn],son[maxn],mark[maxn],dist[maxn],w[maxn],val[maxn],b[maxn];
    query q[maxq];
    int cur;
    void init(int n){
        this->n=n;
        m=0;
        memset(first,0,sizeof(first));
    }
    void addedge(int from,int to,int cost){
        e[++m]=(edge){to,cost,first[from]};
        first[from]=m;
    }
    void dfs(int u){
        sz[u]=1;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (dep[v])
                continue;
            fa[v]=u;
            dep[v]=dep[u]+1;
            dist[v]=dist[u]+e[i].cost;
            w[v]=e[i].cost;
            dfs(v);
            sz[u]+=sz[v];
            if (!son[u] || sz[v]>sz[son[u]])
                son[u]=v;
        }
    }
    void dfs2(int u,int tp){
        top[u]=tp;
        b[++cur]=u;
        if (son[u])
            dfs2(son[u],tp);
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (!top[v])
                dfs2(v,v);
        }
    }
    void prepare(){
        dep[1]=1;
        dist[1]=0;
        fa[1]=-1;
        dfs(1);
        cur=0;
        dfs2(1,1);
        cur=0;
    }
    int lca(int u,int v){
        for(;top[u]!=top[v];u=fa[top[u]])
            if (dep[top[u]]<dep[top[v]])
                swap(u,v);
        return dep[u]<dep[v]?u:v;
    }
    void addquery(int u,int v){  //O(log n)
        int lc=lca(u,v);
        q[++cur]=(query){u,v,lc,dist[u]+dist[v]-2*dist[lc]};
    }
    int num,mmax;
    bool check(int x){  //O(n)
        memset(mark,0,sizeof(mark));
        memset(val,0,sizeof(val));
        num=mmax=0;
        for(int i=1;q[i].len>x && i<=cur;i++){
            num++;
            mark[q[i].u]++;
            mark[q[i].v]++;
            mark[q[i].lc]-=2;
        }
        //puts("WTF");
        for(int i=n;i>=2;i--){
            val[b[i]]+=mark[b[i]];
            if (val[b[i]]==num)
                mmax=max(mmax,w[b[i]]);
            val[fa[b[i]]]+=val[b[i]];
        }
        //printf("check(%d)=%d\n",x,(q[1].len-mmax)<=x);
        return (q[1].len-mmax)<=x;
    }
    int get(){ //O(nlogn)
        sort(q+1,q+cur+1);
        //binary search
        int low=0,high=q[1].len+1;
        while(low<high){
            int mid=(low+high)/2;
            if (check(mid))
                high=mid;
            else low=mid+1;
        }
        return low;
    }
}g;
int main(){
    init();
    int n=readint(),m=readint();
    g.init(n);
    for(int i=1;i<=n-1;i++){
        int x=readint(),y=readint(),z=readint();
        g.addedge(x,y,z);
        g.addedge(y,x,z);
    }
    g.prepare();
    //puts("WTF");
    for(int i=1;i<=m;i++){
        int u=readint(),v=readint();
        g.addquery(u,v);
    }
    //puts("WTF");
    printf("%d\n",g.get());
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2016/07/22/uoj150/

隐藏