동적 dp 학습 소기

이 물건은 WC2018에서 말했는데 왜 전혀 기억이 안 나지?겨울잠을 자고 있었을 거예요.
NOIP2018T6는 동적 dp로 보면 하나의 누드 문제이지만 질문은 서로 독립된 것이다. 즉, 수정은 시효성이 없기 때문에 동적 dp를 배증으로 대체할 수 있다.
먼저 한 문제를 봅시다.
P4719 [템플릿] 동적 dp
만약 수정하지 않았다면, 이 문제는 바로 나무 모양 dp 입문 문제: 상사 없는 파티
f(x, 0/1) f(x, 0/1) f(x, 0/1)는 각각 x를 뿌리로 하는 하위 트리에서 x의 최대 독립 집합을 선택하고 x의 최대 독립 집합을 선택하지 않는다는 것을 나타낸다.
f(x, 0)= ∑y∈son(x)m a x(f(y, 0), f(y, 1) f (x, 0)=\sum{y∈son(x)}max(f(y,0),f(y,1)) f(x,0)=∑y∈son(x)​max(f(y,0),f(y,1)) f ( x , 1 ) = v [ x ] + ∑ y ∈ s o n ( x ) f ( y , 0 ) f(x,1)=v[x]+\sum_{y∈son(x)}f(y,0) f(x,1)=v[x]+∑y∈son(x)​f(y,0)
현재 우리는 점 x의 권한 값 v를 수정해야 한다. 이 수정은 분명히 x가 루트 경로에 있는 모든 점의 f에만 영향을 미칠 뿐이다. 문제는 어떻게 신속하게 수정하는가이다.
하나의 경로를 수정한 이상 우리는 나무 사슬의 분할을 생각해 볼 수 있다.
g(x, 0/1)g(x, 0/1)g(x, 0/1)를 설정하면 x가 뿌리인 자수에서 무거운 아들의 자수를 삭제한 x선(1)/불선(0)의 최대 독립집을 의미한다.
x에서 루트로 가는 경로의 수정에 대해 g g g가 영향을 받은 것은 분명히 x와 모든 무거운 체인의 아버지뿐이었다.
무거운 체인은 log줄만 있기 때문에 폭력적으로 수정하면 됩니다.
그렇다면 무거운 체인의 dp 이전을 어떻게 빠르게 할 것인가에 대한 질문은 다음과 같다. f(i, 0)= g(i, 0)= g(i, 0) + m a x(f(i+1, 0), f(i+1, 1), f(i+1, 1) f(i, 0)= g(i, 0) + max(f(i+1, 0) + max(f(i+1, 0), f(i+1, 1) f(i+1, 1, 1) f(i, 0) f(i, 0) = f(i, 0) = g(i, 0) = g(i, 0) + 10) + max(f(i+1, 0) (i+1, 1) (i+1, 1) (i+1, 1) (i+1, 1) (i, 1) = i, 1 = i, 1 + 1 = i, 1 + 1 + 1 = i, f) 1 + 1 + 1 (f) 1 + 1 + 1 g(i,1)+f(i+1,0)f(i,1)=g(i,1)+f(i+1,0)는 편의를 위해 i와 i+1은 체인에 인접한 두 점을 대표한다.
다음은 고양이 고기의 기이한 기법을 도입해야 한다. 우리는 매트릭스 곱셈법을 알고 있다. 현재 우리는 새로운 매트릭스 곱셈법을 정의할 것이다. 예를 들어 C=A ∗ B C=A*B C=A 𕓭 B는 C(i, j) = m a x(A, k) + B(k, k) + B(k, j))) (1<=k <=n) C(i, j) = max(i, j) = max(A, i, k) + B(k, j) + B(k, j))) (1<=k, k==n) + i, j) (k, j) + j)) (k, b) (k, b) + j) (k, b) (k, b) (k, k) (k, k) + j) (k) (k) (k) (k=k<=n)
이 행렬 곱셈도 오른쪽 결합률을 만족시킨다는 것을 증명하기 쉽다.
dp를 매트릭스 곱셈으로 전환: [f(i, 0), f(i, 1)] = [g(i, 0), g(i, 1)] [f(i+1, 0), f(i+1, 0), f(i+1, 0), f(i+1, 0) = [f(i+1, 1), -4∞] [f(i, 0), f(i, i, 1)] = [g(i, 0), g(i, 0), g(i, 1, 1)] *\bigl[\begi[\begigiinx 1, 1), f(i+ 1, 1) [f(i+1, i, f(i, 1, 1) = = = = = = [g(i, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, f, f, f, f,++ 1) + 1 + 1 + 1 + 1 = = = = = = = = = = = = = = dp dp를 행렬 dp{matrix}\bigr] [f(i,0), f(i,1)] = [g(i,0), g(i,1)] [f(i+1,0), f(i+1,1), f(i+1,1), f(i+1,1), f(i+1,0)--∞]
그러면 각 점의 행렬은 [g(x, 0), g(x, 0)g(x, 1)+v[x], -3∞]\bigl[\begin{matrix}g(x, 0), &g(x, 0)\g(x, 1)+v[x], &-∞\end{matrix}\bigr] [g(x, 0), g(x, 1)+v[x], g(x, 0)-∞]
세그먼트 트리로 구간 매트릭스 곱셈을 유지하면 한 점의 fff를 빠르게 얻을 수 있습니다.
시간 복잡도 O(n l o g 2 n) O(n~log^2n) O(n log2n).
Code:

#include
#include
#define ll long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define FB for(int i = fi[x], y = to[i]; i; y = to[i = nt[i]])
#define i0 i << 1
#define i1 i << 1 | 1
#define pp printf
using namespace std;

const int N = 1e5 + 5;

int n, m, v[N];
int x, y, fi[N], to[N * 2], nt[N * 2], tot;

void link(int x, int y) { nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;}

int dep[N], fa[N], siz[N], son[N], top[N];

void dg(int x) {
    siz[x] = 1; dep[x] = dep[fa[x]] + 1;
    FB if(y != fa[x])
        fa[y] = x, dg(y), siz[x] += siz[y],
        son[x] = siz[son[x]] > son[y] ? son[x] : y;
}

int w[N], tw[N], cntw;

void dfs(int x) {
    w[x] = tw[x] = ++ cntw;
    if(son[x]) top[son[x]] = top[x], dfs(son[x]), tw[x] = tw[son[x]];
    FB if(y != fa[x] && y != son[x])
        top[y] = y, dfs(y);
}

const int inf = 2147483647;

struct jz {
    ll a[2][2];
    jz() { memset(a, 0, sizeof a);}
};

jz operator *(jz a, jz b) {
    jz c;
    c.a[0][0] = max(a.a[0][0] + b.a[0][0], a.a[0][1] + b.a[1][0]);
    c.a[0][1] = max(a.a[0][0] + b.a[0][1], a.a[0][1] + b.a[1][1]);
    c.a[1][0] = max(a.a[1][0] + b.a[0][0], a.a[1][1] + b.a[1][0]);
    c.a[1][1] = max(a.a[1][0] + b.a[0][1], a.a[1][1] + b.a[1][1]);
    return c;
}

int pl, pr, px; jz pj;

jz t[N * 4], f[N];

void add(int i, int x, int y) {
    if(y < pl || x > pr) return;
    if(x == y) { t[i] = f[x]; return;}
    int m = x + y >> 1; add(i0, x, m); add(i1, m + 1, y);
    t[i] = t[i0] * t[i1];
}

void ft(int i, int x, int y) {
    if(y < pl || x > pr) return;
    if(x >= pl && y <= pr) { pj = pj * t[i]; return;}
    int m = x + y >> 1; ft(i0, x, m); ft(i1, m + 1, y);
}

jz ask(int x) {
    pj.a[0][0] = pj.a[1][1] = 0;
    pj.a[0][1] = pj.a[1][0] = -inf;
    pl = w[x], pr = tw[x]; ft(1, 1, n); return pj;
}

void xiu(int x, int lv, int nv) {
    f[w[x]].a[1][0] += nv - lv;
    jz la, nw;
    while(x) {
        la = ask(top[x]);
        pl = pr = w[x]; add(1, 1, n);
        nw = ask(top[x]);
        x = fa[top[x]];
        f[w[x]].a[0][0] += max(nw.a[0][0], nw.a[1][0]) - max(la.a[0][0], la.a[1][0]);
        f[w[x]].a[0][1] = f[w[x]].a[0][0];
        f[w[x]].a[1][0] += nw.a[0][0] - la.a[0][0];
    }
}

int main() {
    scanf("%d %d", &n, &m);
    fo(i, 1, n) scanf("%d", &v[i]);
    fo(i, 1, n - 1)	{
        scanf("%d %d", &x, &y);
        link(x, y); link(y, x);
    }
    dg(1); top[1] = 1; dfs(1);
    fo(i, 1, n) f[i].a[1][1] = -inf;
    fo(i, 1, n) xiu(i, 0, v[i]);
    fo(ii, 1, m) {
        scanf("%d %d", &x, &y);
        xiu(x, v[x], y); v[x] = y;
        pj = ask(1);
        printf("%lld
", max(pj.a[0][0], pj.a[1][0]));
    }
}