欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ1935: [Shoi2007]Tree 园丁的烦恼(树状数组 二维数点)

程序员文章站 2022-05-29 10:56:06
题意 "题目链接" Sol 二维数点板子题 首先把询问拆成四个矩形 然后离散化+树状数组统计就可以了 cpp include define int long long define LL long long using namespace std; const int MAXN = 1e6 + 10 ......

题意

题目链接

sol

二维数点板子题

首先把询问拆成四个矩形

然后离散化+树状数组统计就可以了

#include<bits/stdc++.h> 
#define int long long 
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 3e18 + 10;
const double eps = 1e-9;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
template <typename a> inline void debug(a a){cout << a << '\n';}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, t, fa[maxn], d[maxn], pp[maxn], qq[maxn], lim[maxn], siz[maxn], sum, vis[maxn], mx, root, f[maxn], st[maxn], top, cnt;
vector<int> v[maxn];
void dfs(int x) {
    d[x] += d[fa[x]]; siz[x] = 1;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i]; if(to == fa[x]) continue;
        dfs(to); siz[x] += siz[to];
    }
}
void find(int x) {
    //printf("%d\n", x);
    int mx = 0; siz[x] = 1;
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i]; if(to == fa[x] || vis[to]) continue;
        find(to); siz[x] += siz[to];
        chmax(mx, siz[to]); 
    }
    chmax(mx, sum - siz[x]);
    if(mx < mx && siz[x] > 1) mx = mx, root = x;
}
struct node {
    int id, dis;
    bool operator < (const node &rhs) const {
        return dis > rhs.dis;
    }
}a[maxn];
void dfs2(int x) {
    a[++cnt].id = x;
    a[cnt] = (node) {x, d[x] - lim[x]};
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i]; if(to == fa[x] || vis[to]) continue;
        dfs2(to);
    }
}
int y(int x) {
    return f[x];
}
int x(int x) {
    return d[x];
}
double slope(int x, int y) {
    return (double) (y(y) - y(x)) / (x(y) - x(x));
} 
void insert(int x) {
    while(top > 1 && slope(st[top], x) > slope(st[top - 1], st[top])) top--;
    st[++top] = x;
}
int search(double x, int id) {
    if(!top) return inf;
    int l = 1, r = top - 1, ans = 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if((slope(st[mid], st[mid + 1]) >= x)) ans = mid + 1, l = mid + 1;
        else r = mid - 1;
    }
    return f[st[ans]] - d[st[ans]] * pp[id];
}
void solve(int x, int tot, int up) {
    vector<int> pot;
    for(int t = x; t != up; t = fa[t]) 
        pot.push_back(t);
    cnt = 0; 
    for(int i = 0; i < v[x].size(); i++) {
        int to = v[x][i]; if(to == fa[x]) continue;
        dfs2(to);//dep´ó´óµ½´ï𡣬dis´ó´óµ½ð¡
    }
    sort(a + 1, a + cnt + 1);
    int now = 0; top = 0;
    for(int i = 1; i <= cnt; i++) {
        int cur = a[i].id;
        while(now <= pot.size() - 1 && d[pot[now]] >= a[i].dis) insert(pot[now++]);
        chmin(f[cur], search(pp[cur], cur) + qq[cur] + d[cur] * pp[cur]);
    }
}
void work(int x, int tot) {
    if(tot == 1) return ;
    root = x; sum = tot; mx = sum; find(root);
    int rt = root;
    for(int i = 0; i < v[rt].size(); i++) {
        int to = v[rt][i]; if(to == fa[rt]) continue;
        vis[to] = 1;
    }
    work(x, tot - siz[root] + 1);
    solve(rt, tot, fa[x]);
    for(int i = 0; i < v[rt].size(); i++) {
        int to = v[rt][i]; if(to == fa[rt]) continue;
        work(to, siz[to]);
    }   
}
signed main() {
    //freopen("a.in", "r", stdin);
    n = read(); t = read();
    for(int i = 2; i <= n; i++) {
        fa[i] = read();
        v[fa[i]].push_back(i); v[i].push_back(fa[i]);
        d[i] = read(); pp[i] = read(); qq[i] = read();  lim[i] = read();
    }
    dfs(1);
    memset(f, 0x7f7f7f, sizeof(f)); f[1] = 0;
    work(1, n);
    for(int i = 2; i <= n; i++) cout << f[i] << '\n';
    return 0;
}
/*
7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10
*/