A simple Blog for wyx I've been down the bottle hoping.
3672: [Noi2014]购票 树链剖分 线段树 凸包 三分 斜率优化 点分治
发表于: | 分类: Oi | 评论:0 | 阅读:54

我要死了 调了三个小时最后发现是因为算叉积的时候爆long long ,日死出题人!

咳咳

首先我们把所有点到根变成根到所有点,然后变成了一个大力$dp$

$f(i) = min(f(j)+calc(j,i))$

$f(i) = min(f(j)+(len(i)-len(j))\times P[i]+Q[i])$

$f(i) = min(f(j)+P[i]\times len(i) - P[i]\times len(j) + Q[i])$

$f(j) = f(i) - P[i] \times len(i) + P[i] \times len(j) - Q[i]$

然后你就可以看成是平面内的一个点一个点(len(j),f(j)),f(i)其实就是截距,然后最小化f(j)显然维护下凸包三分

然后我们大力树剖一下就行了

每个节点挂上该部位的所有的点构成的凸包就行了复杂度$n\log^3{n}$

我真的写了这个程序然后在BZ上A了

当然出题人肯定不是想让你卡常数的……

我们考虑这个东西是一个有根树,然后我们进行有根树的点分治即可,对于一条链大力斜率优化一下就可以了,复杂度少了一个线段树的log

更为具体的做法移步大爷题解

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
typedef double f2;
typedef long long LL;
const int N = 2e5+5;
const int M = N << 2;
const LL inf = 1e18;
inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int head[N] , n, T;

struct graph {
    int next, to, val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next), to(_to), val(_val) {}
}edge[M];

inline void add(int x,int y,int z) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z); head[x] = cnt;
    edge[++cnt] = graph(head[y], x, z); head[y] = cnt;
}

int size[N], top[N], fa[N][23], depth[N], w[N];
LL dis[N];

inline void DFS1(int x) {
    size[x] = 1;
    for(int i=head[x];i;i=edge[i].next) 
        if(edge[i].to != fa[x][0]) {
            fa[edge[i].to][0] = x;
            depth[edge[i].to] = depth[x] + 1;
            dis[edge[i].to] = dis[x] + edge[i].val;
            DFS1(edge[i].to);
            size[x] += size[edge[i].to];
        }
}

inline void DFS2(int x,int chain) {
    static int cnt = 0;
    w[x] = ++cnt, top[x] = chain; int k = 0;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa[x][0] && size[k] < size[edge[i].to]) k = edge[i].to;
    }
    if(!k) return;
    DFS2(k,chain);
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa[x][0] && edge[i].to != k) {
            DFS2(edge[i].to, edge[i].to);
        }
    }
}

struct poi {
    LL x, y;
    poi (LL _x=0, LL _y=0):x(_x),y(_y){}
    poi operator + (const poi &z) const{return poi(x+z.x,y+z.y);}
    poi operator - (const poi &z) const{return poi(x-z.x,y-z.y);}
    f2  operator ^ (const poi &z) const{return (f2)x*z.y-(f2)y*z.x;}
    bool operator < (const poi &z) const {
        return x != z.x ? x < z.x : y < z.y;
    }
} p[N], temp[N]; 

LL P[N], Q[N],L[N];

struct seg {
    vector <poi> V;
    int size;
    bool flag;
} tr[N<<2];

inline LL calc(int k,int j,int id) {

    return tr[k].V[j].y + P[id] * (dis[id] - tr[k].V[j].x) + Q[id];
}

inline void build(int k,int l,int r) {
    int top = 0;
    for(int i=l;i<=r+1;++i) tr[k].V.pb(poi(0,0));
    for(int i=l;i<=r;++i) temp[++top] = p[i];
    sort(temp+1,temp+top+1);
    tr[k].size = 0;
    for(int i=1;i<=top;++i) {
        while(tr[k].size > 1 && ((temp[i]-tr[k].V[tr[k].size])^(tr[k].V[tr[k].size]-tr[k].V[tr[k].size-1])) >= 0 )
            --tr[k].size;
        tr[k].V[++tr[k].size] = temp[i];
    } 
}

LL ask(int k,int id) {
    LL ans = inf;
    int l = 1, r = tr[k].size;
    while(r - l >= 3) {
        int mid1 = l+(r-l)/3, mid2 = r-(r-l)/3;
        if(calc(k,mid1,id) < calc(k,mid2,id)) r = mid2;
        else l = mid1;
    }
    for(int j=l;j<=r;++j) ans = min(ans, calc(k,j,id));
    return ans;
}

LL ask(int k,int l,int r,int x,int y,int id) {
    if(x <= l && r <= y) {
        if(!tr[k].flag) {
            tr[k].flag = 1;
            build(k,l,r);
        }
        return ask(k ,id);
    }
    int mid = (l+r) >> 1;
    LL ans = inf;
    if(x <= mid) ans = min(ans, ask(k<<1,l,mid,x,y,id));
    if(mid < y) ans = min(ans, ask(k<<1|1,mid+1,r,x,y,id));
    return ans;
}

LL ask(int x,int y,int id) {
    LL ans = inf;
    while(depth[top[x]] > depth[y]) {
        ans = min(ans, ask(1,1,n,w[top[x]], w[x], id));
        x = fa[top[x]][0];
    }
    ans = min(ans, ask(1,1,n,w[y],w[x], id));
    return ans;
}

int pre[N];
LL F[N];

inline int up(int x) {
    int ans = x;
    for(int i=22;~i;--i) {
        if(fa[ans][i] && dis[x] - dis[fa[ans][i]] <= L[x]) ans = fa[ans][i];
    }   
    return ans;
}

int main() {
//  freopen("tt.in","r",stdin);
//  freopen("ticket.in","r",stdin);
//  freopen("ticket.out","w",stdout);
    n = read(), T = read();
    for(int i=2;i<=n;++i) {
        fa[i][0] = read();
        int val = read();
        P[i] = read(), Q[i] = read(), L[i] = read();
        add(fa[i][0], i, val);
    }
    DFS1(1);
    DFS2(1,1);
    for(int j=1;j<=22;++j) for(int i=1;i<=n;++i) fa[i][j] = fa[fa[i][j-1]][j-1];
    for(int i=1;i<=n;++i) 
        pre[i] = up(i);
    F[1] = 0; p[w[1]] = poi(0,0);
    for(int i=2;i<=n;++i) {
        F[i] = ask(fa[i][0], pre[i], i);
        p[w[i]] = poi(dis[i], F[i]);
        printf("%lld\n",F[i]);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP