Rockdu's Blog

题目描述

给定一棵n个点的树，点带点权。

有$m$次操作，每次操作给定$x,y$，表示修改点$x$的权值为$y$。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入输出格式

输入格式：

第一行，$n,m$，分别代表点数和操作数。

第二行，V1​,V2​,...,Vn​，代表$n$个点的权值。

接下来$n-1$行，$x,y$，描述这棵树的$n-1$条边。

接下来$m$行，$x,y$，修改点$x$的权值为$y$。

输出格式：

对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。

保证答案在$int$范围内

输入输出样例

10 10
-11 80 -99 -76 56 38 92 -51 -34 47 
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93

186
186
190
145
189
288
244
320
258
304

说明

对于30%的数据，$1\le n,m\le 10$

对于60%的数据，$1\le n,m\le 1000$

对于100%的数据，$1\le n,m\le 100000$

$考场上其实想过树链剖分维护矩阵乘积，觉得联赛不会考的这么毒没有继续往下想了。$

$想不到出题人是个毒瘤\dots \dots 唉\dots \dots$

$于是就是这样了，树链剖分把轻链看成常数写进转移，在重链上dp维护矩阵乘积。$

#include<cstdio>
#include<algorithm>
#include<cstring>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, next;
} e[maxn << 1];
int head[maxn], cnt, n, m, u, v, w[maxn], MXR[maxn];
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}
struct MAT {int d[2][2];};
MAT tmp;
MAT operator * (const MAT & A, const MAT & B) {
    tmp = (MAT){-inf, -inf, -inf, -inf};
    For(i, 0, 1) For(j, 0, 1) For(k, 0, 1)
        tmp.d[i][j] = max(A.d[k][j] + B.d[i][k], tmp.d[i][j]);
    return tmp;
}

int siz[maxn], fa[maxn], top[maxn], son[maxn], d[maxn];
int dfn[maxn], org[maxn], dcnt, dp[maxn][2], ldp[maxn][2];
void dfs1(int u, int p) {
    siz[u] = 1;
    fa[u] = p, d[u] = d[p] + 1;
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == p) continue;
        dfs1(v, u), siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[v])
            son[u] = v;
    }
}

void work(int u) {
    ldp[u][1] = dp[u][1] = w[u];
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u]) continue;
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u] || v == son[u]) continue;
        ldp[u][0] += max(dp[v][0], dp[v][1]);
        ldp[u][1] += dp[v][0];
    }
}

int dfs2(int u, int tp) {
    dfn[u] = ++dcnt;
    org[dfn[u]] = u;
    top[u] = tp, MXR[u] = u;
    if(son[u]) MXR[u] = dfs2(son[u], tp);
    for(register int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
    work(u);
    return MXR[u];
}

namespace SGT {
    MAT t[maxn << 2];
    void push_up(int rt) {
        t[rt] = t[rt << 1 | 1] * t[rt << 1];
    }
    void build(int l, int r, int rt) {
        if(l == r) {
            t[rt] = (MAT) {ldp[org[l]][0], ldp[org[l]][0], 
                            ldp[org[l]][1], -inf};
            rt;
            return ;
        }
        int mid = l + r >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        push_up(rt);
    }
    void edit(int x, int tl, int tr, const MAT &nw, int rt) {
        if(tl == tr) {
            t[rt] = nw;
            return ;
        }
        int mid = tl + tr >> 1;
        if(x <= mid) edit(x, tl, mid, nw, rt << 1);
        else edit(x, mid + 1, tr, nw, rt << 1 | 1);
        push_up(rt);
    }
    MAT query(int l, int r, int tl, int tr, int rt) {
        if(l == tl && r == tr) return t[rt];
        int mid = tl + tr >> 1;
        if(r <= mid) return query(l, r, tl, mid, rt << 1);
        else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
        else return query(mid + 1, r, mid + 1, tr, rt << 1 | 1) * 
                    query(l, mid, tl, mid, rt << 1);
    }
}

int Q() {
    MAT ans = SGT::query(1, dfn[MXR[1]], 1, n, 1);
    return max(ans.d[0][0], ans.d[1][0]);
}

void Ref(int x, int dp0, int dp1) {
    ldp[fa[x]][0] -= max(dp[x][0], dp[x][1]);
    ldp[fa[x]][1] -= dp[x][0];
    dp[x][0] = dp0, dp[x][1] = dp1;
    ldp[fa[x]][0] += max(dp[x][0], dp[x][1]);
    ldp[fa[x]][1] += dp[x][0];
}

void E(int x, int W) {
    ldp[x][1] -= w[x];
    ldp[x][1] += (w[x] = W);
    while(x) {
        SGT::edit(dfn[x], 1, n, (MAT) {ldp[x][0], ldp[x][0], 
                                        ldp[x][1], -inf}, 1);
        x = top[x];
        tmp = SGT::query(dfn[x], dfn[MXR[x]], 1, n, 1);
        Ref(x, tmp.d[0][0], tmp.d[1][0]);
        x = fa[x];
    }
} 

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    for(register int i = 1; i < n; ++i)
        scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
    dfs1(1, 0), dfs2(1, 1), SGT::build(1, n, 1);
    //printf("%d\n", Q());
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        E(u, v);
        printf("%d\n", Q());
    }
    return 0;
}