【BZOJ5129】【Lydsy1712月赛】树上传送

点分治+最短路即可。

首先看到距离不超过某个数的限制可以想到点分治。

我们建出原树的点分树,对于每个根我们bfs一遍,得到它子树中的节点到根的距离以及按到根的距离排序后的序列。

考虑Dijkstra算法,传统的Dijkstra中每个点可能被松弛成功多次,但是这题每个点所有出边的权值都是相同的,我们每次取wi=disi+costiw_i=dis_i+cost_i最小的点出来松弛,就可以保证每个点第一次被松弛成功就是最优的,于是我们可以将这个点删去。

这样我们每次拿出来wiw_i最小的点uu,枚举其和要松弛的点的lcalca,将其子树中的点按照距离从小到大松弛就可以了。具体实现时类似当前弧。

至于点分治的写法,安利11Dimensions的写法QwQ

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5129.txt","r",stdin);
        freopen("5129.out","w",stdout);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=300002;
const int maxm=600002;
const int nlgn=maxn*20;
struct graph{
    int n,m;
    struct edge{
        int to,next;
    }e[maxm];
    int first[maxn];
    void addedge(int from,int to){
        e[++m]=(edge){to,first[from]};
        first[from]=m;
    }
    int sz[maxn];
    bool vis[maxn];
    int d[maxn][21];
    int gs(int u,int fa){
        sz[u]=1;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (v!=fa && !vis[v])
                sz[u]+=gs(v,u);
        }
        return sz[u];
    }
    int h;
    int ctrd(int u,int fa){
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (v!=fa && !vis[v] && sz[v]>h)
                return ctrd(v,u);
        }
        return u;
    }
    int qwq[nlgn];
    int st[maxn],en[maxn],cur;
    int dep[maxn];
    void bfs(int s,int ly){
        cur++;
        int l=cur,r=cur;
        qwq[cur]=s;
        d[s][ly]=0;
        while(l<=r){
            int u=qwq[l++];
            for(int i=first[u];i;i=e[i].next){
                int v=e[i].to;
                if (d[v][ly]!=-1 || vis[v])
                    continue;
                d[v][ly]=d[u][ly]+1;
                qwq[++r]=v;
            }
        }
        cur=r;
    }
    int f[maxn];
    int dcomp(int u,int ly){
        h=gs(u,0)/2;
        int rt=ctrd(u,0);
        vis[rt]=1;
        st[rt]=cur+1;
        dep[rt]=ly;
        bfs(rt,ly);
        en[rt]=cur;
        for(int i=first[rt];i;i=e[i].next){
            int v=e[i].to;
            if (!vis[v])
                f[dcomp(v,ly+1)]=rt;
        }
        return rt;
    }
    priority_queue<pli,vector<pli>,greater<pli> > q;
    int lim[maxn],cost[maxn];
    ll w[maxn];
    void dijkstra(int s){
        memset(w,0x3f,(n+1)*8);
        w[s]=cost[s];
        q.push(make_pair(w[s],s));
        while(!q.empty()){
            pli p=q.top();
            q.pop();
            int u=p.second,tat=u;
            while(u){
                for(int& i=st[u];i<=en[u];i++){ //看起来很像当前弧?喵啊
                    int v=qwq[i];
                    int dis=d[tat][dep[u]]+d[v][dep[u]];
                    if (dis>lim[tat])
                        break;
                    if (p.first+cost[v]<w[v]){
                        w[v]=p.first+cost[v];
                        q.push(make_pair(w[v],v));
                    }
                }
                u=f[u];
            }
        }
    }
    void work(int s){
        memset(d,-1,sizeof(d));
        dcomp(1,0);
        dijkstra(s);
    }
}g;
int main(){
    init();
    int n=g.n=readint(),s=readint();
    for(int i=1;i<n;i++){
        int u=readint(),v=readint();
        g.addedge(u,v);
        g.addedge(v,u);
    }
    for(int i=1;i<=n;i++)    
        g.lim[i]=readint(),g.cost[i]=readint();
    g.work(s);
    for(int i=1;i<=n;i++)
        printf("%lld\n",g.w[i]-g.cost[i]);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2018/04/03/bzoj5129/

隐藏