BJOI 模拟赛 #3 题解

佚名 6年前 (2019-04-14) 随笔 626人围观抢沙发百度已收录

一个网格，每个点有权值，求有多少条路径权值乘积不小于 $n$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

$R,C \leq 300, n \leq 10^6$

sol：

暴力 dp 是 $O(R \times C \times n)$ 的

然后发现如果一条路径大于 $n$ ，直接把它设成 $n$ 即可，然后又发现 $\lfloor \frac{n}{i} \rfloor$ 只有 $O(\sqrt{n})$ 种取值，记录一下即可做到 $O(R \times C \times n)$

一个有点权和边权的树，一条简单路径合法当且仅当对于这个路径的每一个非空前缀都满足点权大于等于边权，求有多少合法简单路径

$n \leq 100000$

sol：

点分治，预处理一下子树里每个点到重心会剩下多少点权，重心到子树里每个点还需要多少点权，在重心处双指针合并一下，容斥即可

#include <bits/stdc++.h>
#define LL long long
#define debug(x) cerr << #x << " = " << x
#define TAB cerr << " "
#define EDL cerr << endl
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
    int x = 0,f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar())if(ch == '-') f = -f;
    for(; isdigit(ch); ch = getchar())x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 100010;
int n, a[maxn];
LL ans;
int first[maxn], to[maxn << 1], nx[maxn << 1], val[maxn << 1], cnt;
inline void add(int u, int v, int w) {
    to[++cnt] = v;
    nx[cnt] = first[u];
    first[u] = cnt;
    val[cnt] = w;
}
int root, sig, ff[maxn], size[maxn], vis[maxn];
void findroot(int x, int pre) {
    ff[x] = 0; size[x] = 1;
    for(int i=first[x];i;i=nx[i]) {
        if(to[i] == pre || vis[to[i]]) continue;
        findroot(to[i], x); size[x] += size[to[i]];
        ff[x] = max(ff[x], size[to[i]]);
    }
    ff[x] = max(ff[x], sig - size[x]);
    if(ff[x] < ff[root]) root = x;
}
LL f[maxn], g[maxn]; int fl, gl;
void calup(int x, int pre, LL cur, LL mx) {
    if(a[x] >= mx) f[++fl] = (a[x] + cur); mx -= a[x], cur += a[x];
    for(int i=first[x];i;i=nx[i]) {
        if(vis[to[i]] || to[i] == pre) continue;
        calup(to[i], x, cur - val[i], max(mx + val[i], (LL)val[i]));
    }
}
void caldw(int x, int pre, LL cur, LL mn) {
    //debug(mn); TAB; debug(cur); EDL;
    g[++gl] = mn; cur += a[x];
    for(int i=first[x];i;i=nx[i]) {
        if(vis[to[i]] || to[i] == pre) continue;
        caldw(to[i], x, cur - val[i], min(mn, cur - val[i]));
    }
}
void merge(int opt) {
    int tmp = 0, pos = fl; LL res = 0;
    //cerr << fl << " " << gl << endl;
//    debug(fl); TAB; debug(gl); EDL;
    sort(f + 1, f + fl + 1); sort(g + 1, g + gl + 1);
    rep(i, 1, gl) {
        while(pos && g[i] + f[pos] >= 0) tmp++, pos--;
        res += tmp;
    } ans += opt * res;
//    debug(ans);
}
void solve(int x) {
    fl = gl = 0;
    vis[x] = 1; caldw(x, 0, 0, 0); calup(x, 0, -a[x], 0); merge(1); ans--;
    for(int i=first[x];i;i=nx[i]) {
        if(vis[to[i]]) continue; fl = gl = 0;
        caldw(to[i], x, a[x] - val[i], a[x] - val[i]);
        calup(to[i], x, -val[i], val[i]); merge(-1);
    }
    for(int i=first[x];i;i=nx[i]) {
        if(vis[to[i]]) continue;
        root = 0; sig = size[to[i]];
        findroot(to[i], x); solve(root); //debug(root);
    }
}
int main() {
    //freopen("transport.in","r",stdin);
    //freopen("transport.out","w",stdout);
    n = read();
    rep(i, 1, n) a[i] = read();
    rep(i, 2, n) {
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
    } ff[0] = 2147483233; sig = n;
    findroot(1, 0); solve(root); //debug(root);
    cout << ans << endl;
}