题目描述
给定一棵n个点的树,点带点权。
有m次操作,每次操作给定x,y,表示修改点x的权值为y。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
输入输出格式
输入格式:
第一行,n,m,分别代表点数和操作数。
第二行,V1,V2,...,Vn,代表nn个点的权值。
接下来n−1行,x,y,描述这棵树的n−1条边。
接下来m行,x,y,修改点x的权值为y。
输出格式:
对于每个操作输出一行一个整数,代表这次操作后的树上最大权独立集。
保证答案在int范围内
输入输出样例
输入样例#1: 复制
- 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
输出样例#1: 复制
- 186
- 186
- 190
- 145
- 189
- 288
- 244
- 320
- 258
- 304
说明
对于30%的数据,1≤n,m≤10
对于60%的数据,1≤n,m≤1000
对于100%的数据,1≤n,m≤100000
考场上其实想过树链剖分维护矩阵乘积,觉得联赛不会考的这么毒没有继续往下想了。
想不到出题人是个毒瘤……唉……
于是就是这样了,树链剖分把轻链看成常数写进转移,在重链上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;
- }
没有帐号? 立即注册