bzoj5210: 최대련 통자 블록과

전송문
이 문제는 바로 동적 dp이다. 먼저 폭력을 고려하면 s는 이 점을 선택하지 않겠다고 하고 f는 이 점을 선택하면 s[i]=max 8289Y(s[t]], f[t]])s[i]=\max(s[t], f[t])s[i]=max(s[t]]=max [t], f[t]) f[i] =max [i] = max [i] = max (0, V x x x++++++ + ∑ f [t] f[i] = =\max (0, V [t] = =\max (0, V++++ + s] =\max [t] =\max (0, V++ + s) =\max (0, V++++++++ +])
처음에는 틀에 따라 곱셈을 썼다.
아니면 경중아들을 분리할지, g는 경아들 f와 중사슬에 g의 서열이 무엇을 의미하는지 놀랍게도 발견 fififi는 i를 머리로 하는 최대 자단과, sisisi는 중연쇄상 서열 g의 최대 자단과 경아들 stst st - max
이것은 분명히 라인 트리 유지보수를 편리하게 사용할 수 있다.수정도 단일 수정으로 바뀌었다. g는 직접 유지보수를 가감할 수 있고, 단일 s는 삭제 가능한 유지보수를 개설할 수 있다.

#include 
#include 
#include 
using namespace std;
 
#define int long long
#define dd c=getchar()
int read() {int s=0,w=1;char c;while (dd,c>'9' || c<'0') if (c=='-') w=-1;while (c>='0' && c<='9') s=s*10+c-'0',dd;return s*w;}
#undef dd
void write(int x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
void wln(int x) {write(x);putchar('
');}void wsp(int x) {write(x);putchar(' ');}
 
const int N = 2e5 + 7;
 
struct edge {
    int t,nxt;
}e[N<<1];
int n,m,cnt;
int V[N],f[N],g[N],s[N];
char c[10];
//=============================================================
int T;
int head[N], siz[N],fa[N],top[N],bot[N],Bs[N],Ms[N],dfn[N],pos[N];
 
void add(int u, int t) {
    e[++cnt].t = t; e[cnt].nxt = head[u]; head[u] = cnt;
}
 
struct heap {
    priority_queue<int> q1,q2;
    void push(int x) {
        q1.push(x);
    }
    void erase(int x) {
        q2.push(x);
    }
    int top() {
        while (!q1.empty() && !q2.empty() && q1.top() == q2.top()) q1.pop(),q2.pop();
        if (q1.empty()) return 0;
        return q1.top();
    }
}Mx[N];
 
void dfs(int x, int F) {
    siz[x] = 1; fa[x] = F;
    for (int i = head[x]; i; i = e[i].nxt) {
        int t = e[i].t;
        if (t == F) continue;
        dfs(t, x);
        siz[x] += siz[t];
        if (siz[t] > siz[Bs[x]]) Bs[x] = t;
    }
}
 
void dfs1(int x, int tp) {
    dfn[++T] = x; pos[x] = T;
    top[x] = tp; bot[x] = x;
    if (Bs[x]) dfs1(Bs[x], tp), bot[x] = bot[Bs[x]] ,s[x] = s[Bs[x]];
    g[x] = V[x];
    for (int i = head[x]; i; i = e[i].nxt) {
        int t = e[i].t;
        if (t == fa[x] || t == Bs[x]) continue;
        dfs1(t, t);
        g[x] += f[t]; Mx[x].push(s[t]);
    }
    f[x] = max(0ll, g[x] + f[Bs[x]]); s[x] = max(s[x], max(f[x], Mx[x].top()));
}
 
//============================================================
 
struct segtree {
    int lc,rc,s,mx;
    segtree() {}
    segtree operator + (segtree a) {
        segtree c;
        c.lc = max(lc, s + a.lc);
        c.rc = max(a.rc, rc + a.s);
        c.s = s + a.s;
        c.mx = max(rc + a.lc, max(mx, a.mx));
        return c;
    }
    #define ls (ts<<1)
    #define rs (ts<<1|1)
    #define lc(x) (tr[x].lc)
    #define rc(x) (tr[x].rc)
    #define s(x) (tr[x].s)
    #define mx(x) (tr[x].mx)
}tr[N<<2];
 
void build(int ts, int l, int r) {
    if (l == r) {
        int x = dfn[l];
        s(ts) = g[x];
        lc(ts) = rc(ts) = max(0ll, g[x]);
        mx(ts) = max(g[x], Mx[x].top());
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid); build(rs, mid+1, r);
    tr[ts] = tr[ls] + tr[rs];
}
 
void insert(int ts, int l, int r, int x) {
    if (l == r) {
        x = dfn[l];
        s(ts) = g[x];
        lc(ts) = rc(ts) = max(0ll, g[x]);
        mx(ts) = max(g[x], Mx[x].top());
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(ls, l, mid, x);
    else insert(rs, mid+1, r, x);
    tr[ts] = tr[ls] + tr[rs];
}
 
segtree query(int ts, int l, int r, int L, int R) {
    if (l == L && r == R) return tr[ts];
    int mid = (l + r) >> 1;
    if (R <= mid) return query(ls, l, mid, L, R);
    else if (L > mid) return query(rs, mid+1, r, L, R);
    else return query(ls, l, mid, L, mid) + query(rs, mid+1, r, mid+1, R);
}
 
void change(int x, int v) {
    segtree t1, t2;
    bool flg=0;
    while (x) {
        if (flg) Mx[x].erase(t1.mx), Mx[x].push(t2.mx);
        t1 = query(1, 1, n, pos[top[x]], pos[bot[x]]);
        flg = 1;
        g[x] += v; 
        insert(1, 1, n, pos[x]);
        t2 = query(1, 1, n, pos[top[x]], pos[bot[x]]);
        v = t2.lc - f[top[x]]; f[top[x]] = t2.lc;//lc±íʾµÄ¾ÍÊÇf[i] 
        x = fa[top[x]];
    }
}
signed main() {
//  freopen("5210.in", "r", stdin);
//  freopen("5210.out", "w", stdout);
    n = read(); m = read();
    for (int i = 1; i <= n; i++) V[i] = read();
    for (int i = 1, u, v; i < n; i++) {
        u = read(), v = read();
        add(u, v); add(v, u);
    }
    dfs(1,0);
    dfs1(1,1);
    build(1, 1, n);
    for (int i = 1, x, v; i <= m; i++) {
        scanf("%s",c);
        if (c[0] == 'M') {
            x = read(), v = read();
            change(x, v - V[x]);
            V[x] = v;
        }
        else {
            x = read();
            wln(query(1, 1, n, pos[x], pos[bot[x]]).mx);        
        }
    }
}