bzoj5210 最大连通子块和 动态 DP + 堆

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=5210

题解

令 (dp[x][0]) 表示以 (x) 为根的子树中的包含 (x) 的连通块的点权和最大值，(dp[x][1]) 为 (x) 的所有孩子中的子树的连通块点权和最大值。

于是有这样的式子：
[ dp[x][0] = max(w_x+sum_{yin child_x} dp[y][0],0)dp[x][1] = max_{yin child_x} max(dp[y][0],dp[y][1]) ]
（其实似乎把 (dp[x][1]) 算上 (dp[x][0]) 的内容也没什么问题，但是我一开始就这样想的不想改了）

现在把这个 (dp) 动态化。令树剖以后，(x) 的重儿子为 (son_x)，(x) 的轻儿子的集合为 (light_x)。令 (h[x][0] = sumlimits_{y in light_x} dp[y][0])，(h[x][1] = maxlimits_{yin light_x} max(dp[y][0],dp[y][1]))。

于是上面的方程可以改写为
[ dp[x][0] = max(w_x+h[x][0] + dp[son_x][0],0)dp[x][1] = max(h[x][1],dp[son_x][1],dp[son_x][0]) ]
于是矩阵（矩乘是把乘法看成加法，加法看成取 (max)）就长这样：
[ begin{bmatrix}h[x][0] + w_x & -infty & 0 0 & 0 & h[x][1] -infty & -infty & 0end{bmatrix} times begin{bmatrix} dp[son_x][0] dp[son_x][1] 0 end{bmatrix} = begin{bmatrix} dp[x][0] dp[x][1] 0 end{bmatrix} ]
然后就套一个动态 DP 的板子就可以了。

有一个需要注意的地方就是因为 (dp[x][1]) 是取 (max) 的，所以在更新 (dp[x][1]) 的时候需要用一个可删除堆来维护最大值。

昨天这道题因为一个 ll 没有写调了几个小时。

单次询问是 (O(log n)) 的，单次修改是 (O(log^2 n))。

#include<bits/stdc++.h>

#define fec(i,x,y) (int i = head[x],y = g[i].to; i; i = g[i].ne,y = g[i].to)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fi first
#define se second
#define pb push_back

template<typename A,typename B> inline char smax(A &a,const B &b) {return a < b ? a = b,1 : 0;}
template<typename A,typename B> inline char smin(A &a,const B &b) {return b < a ? a = b,1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int,int> pii;

template<typename I> inline void read(I &x) {
    int f = 0,c;
    while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
    x = c & 15;
    while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
    f ? x = -x : 0;
}

#define lc o << 1
#define rc o << 1 | 1

const int N = 200000 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n,m,dfc;
int a[N];
int dep[N],f[N],siz[N],son[N],dfn[N],pre[N],top[N],bot[N];
ll dp[N][2],h[N][2],hh[N][2];

struct Heap {
    std::priority_queue<ll> q,p;
    inline void sync() { while (!q.empty() && !p.empty() && q.top() == p.top()) q.pop(),p.pop(); }
    inline void push(ll x) { q.push(x); sync(); }
    inline void del(ll x) { p.push(x),sync(); }
    inline ll top() { sync(); return q.top(); }
    inline bool empty() { sync(); return q.empty(); }
    inline int size() { sync(); return q.size() - p.size·(); }
} q[N];

struct Edge { int to,ne; } g[N << 1]; int head[N],tot;
inline void addedge(int x,int y) { g[++tot].to = y,g[tot].ne = head[x],head[x] = tot; }
inline void adde(int x,int y) { addedge(x,y),addedge(y,x); }

struct Matrix {
    ll a[3][3];
    inline Matrix() { memset(a,sizeof(a)); }
    inline Matrix operator * (const Matrix &b) {
        Matrix c;
        c.a[0][0] = std::max(std::max(a[0][0] + b.a[0][0],a[0][1] + b.a[1][0]),a[0][2] + b.a[2][0]);
        c.a[0][1] = std::max(std::max(a[0][0] + b.a[0][1],a[0][1] + b.a[1][1]),a[0][2] + b.a[2][1]);
        c.a[0][2] = std::max(std::max(a[0][0] + b.a[0][2],a[0][1] + b.a[1][2]),a[0][2] + b.a[2][2]);
        c.a[1][0] = std::max(std::max(a[1][0] + b.a[0][0],a[1][1] + b.a[1][0]),a[1][2] + b.a[2][0]);
        c.a[1][1] = std::max(std::max(a[1][0] + b.a[0][1],a[1][1] + b.a[1][1]),a[1][2] + b.a[2][1]);
        c.a[1][2] = std::max(std::max(a[1][0] + b.a[0][2],a[1][1] + b.a[1][2]),a[1][2] + b.a[2][2]);
        c.a[2][0] = std::max(std::max(a[2][0] + b.a[0][0],a[2][1] + b.a[1][0]),a[2][2] + b.a[2][0]);
        c.a[2][1] = std::max(std::max(a[2][0] + b.a[0][1],a[2][1] + b.a[1][1]),a[2][2] + b.a[2][1]);
        c.a[2][2] = std::max(std::max(a[2][0] + b.a[0][2],a[2][1] + b.a[1][2]),a[2][2] + b.a[2][2]);
        return c;
    }
} t[N << 2];

inline void dfs1(int x,int fa = 0) {
    dep[x] = dep[fa] + 1,f[x] = fa,siz[x] = 1;
    for fec(i,y) if (y != fa) dfs1(y,x),siz[x] += siz[y],siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x,int pa) {
    top[x] = pa,dfn[x] = ++dfc,pre[dfc] = x;
    if (!son[x]) return (void)(bot[x] = x);
    dfs2(son[x],pa),bot[x] = bot[son[x]];
    for fec(i,y) if (y != f[x] && y != son[x]) dfs2(y,y);
}
inline void dfs3(int x,int fa = 0) {
    dp[x][0] = a[x];
    for fec(i,y) if (y != fa) {
        dfs3(y,x);
        dp[x][0] += dp[y][0];
        smax(dp[x][1],std::max(dp[y][1],dp[y][0]));
        if (y != son[x]) h[x][0] += dp[y][0],smax(h[x][1],dp[y][0])),q[x].push(std::max(dp[y][1],dp[y][0]));
    }
    smax(dp[x][0],0);
}

inline void build(int o,int L,int R) {
    if (L == R) {
        int x = pre[L];
        t[o].a[0][0] = h[x][0] + a[x],t[o].a[0][1] = -INF,t[o].a[0][2] = 0;
        t[o].a[1][0] = 0,t[o].a[1][1] = 0,t[o].a[1][2] = h[x][1];
        t[o].a[2][0] = -INF,t[o].a[2][1] = -INF,t[o].a[2][2] = 0;
        return;
    }
    int M = (L + R) >> 1;
    build(lc,L,M),build(rc,M + 1,R);
    t[o] = t[lc] * t[rc];
}
inline void qadd(int o,int R,int x) {
    if (L == R) {
        int x = pre[L];
        t[o].a[0][0] = h[x][0] + a[x],t[o].a[2][2] = 0;
        return;
    }
    int M = (L + R) >> 1;
    if (x <= M) qadd(lc,M,x);
    else qadd(rc,R,x);
    t[o] = t[lc] * t[rc];
}
inline Matrix qsum(int o,int l,int r) {
    if (l <= L && R <= r) return t[o];
    int M = (L + R) >> 1;
    if (r <= M) return qsum(lc,l,r);
    if (l > M) return qsum(rc,r);
    return qsum(lc,r) * qsum(rc,r);
}

inline Matrix qry(int x) { return qsum(1,1,n,dfn[x],dfn[bot[x]]) * Matrix(); }
inline void upd(int x,int k) {
    a[x] = k;
    while (top[x] != 1) {
        Matrix tmp1 = qry(top[x]);
        qadd(1,dfn[x]);
        Matrix tmp2 = qry(top[x]);
        int fa = f[top[x]];
        h[fa][0] += tmp2.a[0][0] - tmp1.a[0][0];
        q[fa].del(std::max(tmp1.a[0][0],tmp1.a[1][0])),q[fa].push(std::max(tmp2.a[0][0],tmp2.a[1][0])),h[fa][1] = q[fa].top();
        x = fa;
    }
    qadd(1,dfn[x]);
}

inline void work() {
    dfs1(1),dfs2(1,1),dfs3(1),build(1,n);
    Matrix tmp;
    while (m--) {
        static char opt[5];
        int x,y;
        scanf("%s",opt);
        if (*opt == 'Q') read(x),tmp = qry(x),printf("%lldn",std::max(tmp.a[0][0],tmp.a[1][0]));
        else read(x),read(y),upd(x,y);
    }
}

inline void init() {
    read(n),read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    int x,y;
    for (int i = 1; i < n; ++i) read(x),adde(x,y);
}

int main() {
#ifdef hzhkk
    freopen("hkk.in",stdin);
#endif
    init();
    work();
    fclose(stdin),fclose(stdout);
    return 0;
}