题解 P1131 [ZJOI2007]时态同步

· · 个人记录

智商不够，数据结构来凑

首先有个显而易见的性质，最后所有的叶子结点的时态都等于初始情况下最大的那个时态。

我们将这个最大的时态记作 maxdep，每个节点 x 被激活的时态记作 dep_x。

那么对于每个叶子结点 d，我们需要在 s\rightarrow d 的链上使用 maxdep-dep_x 次道具。

我们在每个结点 i 上记录一个值 val_i，表示最小情况下 s\rightarrow i 这条链上一共使用了 val_i 次道具。

观察这样一个性质：若有叶子节点 d_1,...,d_k，则最优情况下所有 s\rightarrow d 的交（这个交显然是一条链）上应当使用了最小的 maxdep-dep_d 次道具。

这是因为在公共部分使用道具一定优于分别对每个叶子使用道具，且任何情况下一条链上使用道具的次数+这条链下方任何叶子结点的dep不能大于maxdep。

因此就可以用树链剖分来维护。对于每个叶子节点把 s\rightarrow d 上所有点的权值都关于 d 取一个min。

区间取min？吉司机线段树？不会qwq

我们注意到所有修改操作的端点都在 s （根），那么显然 s\rightarrow d 上所有点的权值是递增的。

那么就好办了，暴力往上跳链即可。

注意到 val_x-val_{fa_x} 的值显然就是边 f_x\rightarrow x 使用道具的次数。

因此最后统计答案的时候差分一下，每条边求和即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define LL long long
#define int long long
extern "C" {
namespace io{
#define BUFS 100000
    static char in[BUFS], *p = in, *pp = in;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
    inline char gtc() {while (isspace(*p)) ++p; return *p++;}
    inline LL read() {
        reg LL x = 0; reg char ch, f = 0;
        while (!isdigit(ch = gc())) f |= ch == '-';
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
        return f ? -x : x;
    }
}}
#define rd io :: read
#define gtc io :: gtc
const int N = 500001; 
int n, s, tot, head[N], siz[N], son[N], top[N], fa[N], dep[N], dfn[N], tim;
struct Edge{int v, w, nxt;} eg[N << 1];
inline void addedge(int u, int v, int w) {
    eg[++tot] = Edge{v, w, head[u]}, head[u] = tot;
}
void dfs1(int x, int Fa, int Dep) {
    fa[x] = Fa, dep[x] = Dep, siz[x] = 1;
    for (reg int i = head[x], v; i; i = eg[i].nxt)
        (v = eg[i].v) != Fa && (
            dfs1(v, x, Dep + eg[i].w),
            siz[x] += siz[v],
            siz[v] > siz[son[x]] && (son[x] = v)
        );
}
void dfs2(int x, int Top) {
    dfn[x] = ++tim, top[x] = Top;
    son[x] && (dfs2(son[x], Top), 0);
    for (reg int i = head[x], v; i; i = eg[i].nxt)
        dfn[v = eg[i].v] || (dfs2(v, v), 0);
}
int seg[N << 2], tag[N << 2];
inline void pushup(int x) {
    seg[x] = min(seg[x << 1], seg[x << 1 | 1]);
}
inline void pushdown(int x) {
    ~tag[x] && (seg[x << 1] = seg[x << 1 | 1] = tag[x << 1] = tag[x << 1 | 1] = tag[x], tag[x] = -1);
}
void assign(int k, int l, int r, int ll, int rr, int v) {
    if (ll > rr) return;
    if (ll <= l && r <= rr) {
        tag[k] = seg[k] = v; return;
    }
    int mid = l + r >> 1;
    pushdown(k);
    ll <= mid && (assign(k << 1, l, mid, ll, rr, v), 0),
    mid < rr && ( assign(k << 1 | 1, mid + 1, r, ll, rr, v), 0);
    pushup(k);
}
int query(int k, int l, int r, int ll, int rr) {
    if (l == r || ll <= l && r <= rr) return seg[k];
    int mid = l + r >> 1, sm = 0x3f3f3f3f;
    pushdown(k);
    ll <= mid && (sm = min(sm, query(k << 1, l, mid, ll, rr))),
    mid < rr && ( sm = min(sm, query(k << 1 | 1, mid + 1, r, ll, rr)));
    return sm;
}
inline void modify(int x, int v) {
    while (x && query(1, 1, n, dfn[top[x]], dfn[x]) >= v)
        assign(1, 1, n, dfn[top[x]], dfn[x], v), x = fa[top[x]];
    if (!x) return;
    int y = x;
    while (x != top[x] && query(1, 1, n, dfn[x], dfn[x]) >= v) x = fa[x];
    assign(1, 1, n, dfn[x] + 1, dfn[y], v);
}
int maxdep;
LL ans;
void dfs3(int x, int Fa) {
    son[x] || (modify(x, maxdep - dep[x]), 0);
    for (reg int i = head[x], v; i; i = eg[i].nxt)
        (v = eg[i].v) != Fa && (dfs3(v, x), 0);
}
void dfs4(int x, int Fa, int Add) {
    for (reg int i = head[x], v, t; i; i = eg[i].nxt)
        (v = eg[i].v) != Fa && (
            t = query(1, 1, n, dfn[v], dfn[v]),
            ans += t - Add,
            dfs4(v, x, t), 0
        );
}
signed main() {
    memset(seg, 0x3f, sizeof seg),
    memset(tag, -1, sizeof tag);
    n = rd(), s = rd();
    for (reg int i = 1, u, v, w; i < n; ++i)
        u = rd(), v = rd(), w = rd(), addedge(u, v, w), addedge(v, u, w);
    dfs1(s, 0, 0), dfs2(s, s);
    for (reg int i = 1; i <= n; ++i) maxdep = max(maxdep, dep[i]);
    dfs3(s, 0), dfs4(s, 0, 0);
    printf("%lld", ans);
    return 0;
}