题目大意：有一棵树，第$i$个点的点权为$s_i(s_1>0)$。初始有每个点都是亮的。$m$次修改，每次改变一个点的亮暗，回答包含$1$的全亮的连通块中点权和最大的连通块的和的值。

题解：不怎么会（我只打了一遍代码），这里是$97$分代码（复杂度$O(n^2log_2n)$，暴力复杂度$O(n^2)$，但是就是$97$。。。）（其实我只是想记录一下我考试的时候写的东西而已，没有任何参考价值）

第一次看题目的时候，把题目理解成了“在$1$所在的连通块中选出一些数，使它们最大”。这不是树剖+线段树+小$DP$吗？

令$w_u=\sum\limits_{v\in u的子树}(s_i\times[s_i>0])$，这可以$O(n)$求出。每次修改一个点$u$，找到它的父亲中第一个暗的（记为$f$）（对于树剖出来的每一条链的时间复杂度是$O(\log_2n)$的），把$w_{[f,u)}$都加上/减去$w_u$值（对于每一条链的时间复杂度也是$O(\log_2n)$的），在输出$w_1$就行了，总复杂度$O(n\log_2^2n)$（挺正常的呀）。

于是我兴冲冲地打了个代码，样例$1$过了（毕竟小样例一般都很简单），我没注意到大样例，就去写$T1$了。

离考试结束还有$30min-$的时候，我回来看了一下$T2$，发现有大样例，于是测了一下，果不其然的挂了，发现题目好像理解错了$QAQ$，开始改。

发现这样的话，对于区间$[f,u)$，若修改后的$w_{i,i\in [f,u)}\leqslant0$，就不会对上面产生贡献，就要$break$掉，而且不一定每一个值都加上/减去了$w_u$（修改前和修改后的$w_i$符号不相等，向上的贡献就会变化），似乎很麻烦。

于是我就记录一下区间的最小值，来判断这个区间是否有会有变号或者不会对上方产生贡献的点的点，修改这个区间，更改一下修改的值，继续操作，直到左端点不亮或者修改前后都小于零

这样，每次修改区间就有$O(n)$个，对于每个区间复杂度$O(\log_2n)$，但是想到这种题目肯定是随机数据（反正一般想不到这比暴力还劣的做法，也就没人卡），限制点的个数一定很少（区间少），于是信仰一交，发现是过了（考试的时候少写一句话没调出来，考试后调的）。

卡点：1.修改区间时，下一个区间的右端点求错（应该是 fa[f] ，写成 fa[dfn[f]] ）。

C++ Code：（$97$分）

#include 
     
      #define maxn 100010const long long inf = 0x7fffffffffffffff;int n, m;long long w[maxn], W[maxn], ANS;int head[maxn], cnt;struct Edge {    int to, nxt;} e[maxn << 1];void addE(int a, int b) {    e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}inline long long max(long long a, long long b) {return a > b ? a : b;}inline long long min(long long a, long long b) {return a < b ? a : b;}namespace ST {    long long tg[maxn << 2], mn[maxn << 2];    bool V[maxn << 2];    inline void update(int rt) {        mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);    }    void build(int rt, int l, int r) {        V[rt] = true;        if (l == r) {            mn[rt] = w[l];            return ;        }        int mid = l + r >> 1;        build(rt << 1, l, mid);        build(rt << 1 | 1, mid + 1, r);        update(rt);    }    inline void pushdown(int rt) {        long long &x = tg[rt];        tg[rt << 1] += x;        tg[rt << 1 | 1] += x;        mn[rt << 1] += x;        mn[rt << 1 | 1] += x;        x = 0;    }    int L, R;    long long num;    void Add(int rt, int l, int r) {        if (L <= l && R >= r) {            mn[rt] += num;            tg[rt] += num;            return ;        }        int mid = l + r >> 1;        if (tg[rt]) pushdown(rt);        if (L <= mid) Add(rt << 1, l, mid);        if (R > mid) Add(rt << 1 | 1, mid + 1, r);        update(rt);    }    void add(int ll, int rr, long long Num) {        L = ll;        R = rr;        num = Num;        Add(1, 1, n);    }    bool modify(int rt, int l, int r, int p) {        if (l == r) return V[rt] = !V[rt];        int mid = l + r >> 1;        bool ans;        if (p <= mid) ans = modify(rt << 1, l, mid, p);        else ans = modify(rt << 1 | 1, mid + 1, r, p);        V[rt] = V[rt << 1] && V[rt << 1 | 1];        return ans;    }    int p;    long long ask(int rt, int l, int r) {        if (l == r) return tg[rt] + w[p];        int mid = l + r >> 1;        if (tg[rt]) pushdown(rt);        if (p <= mid) return ask(rt << 1, l, mid);        else return ask(rt << 1 | 1, mid + 1, r);    }    long long ask(int P) {        p = P;        return ask(1, 1, n);    }    int ans;    bool Query(int rt, int l, int r) {        if (V[rt] && (min(mn[rt], mn[rt] + num) >= 0)) return false;        if (l == r) {            ANS = min(mn[rt] + num, mn[rt]);            if (!V[rt]) ANS = inf;            ans = l;            return true;        }//        if (L <= l && R >= r) return V[rt];        if (tg[rt]) pushdown(rt);        int mid = l + r >> 1;        if (R > mid) if (Query(rt << 1 | 1, mid + 1, r)) return true;        if (L <= mid) if (Query(rt << 1, l, mid)) return true;        return false;    }    int query(int ll, int rr, long long Num) {        L = ll, R = rr, num = Num;        if (Query(1, 1, n)) return ans;        else return ll - 1;    }}int dfn[maxn], idx, top[maxn], son[maxn];int dep[maxn], fa[maxn], sz[maxn], ret[maxn];void dfs1(int u) {    sz[u] = 1;    for (int i = head[u]; i; i = e[i].nxt) {        int v = e[i].to;        if (v != fa[u]) {            fa[v] = u;            dep[v] = dep[u] + 1;            dfs1(v);            sz[u] += sz[v];            if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;        }    }}void dfs2(int u) {    dfn[u] = ++idx;    ret[idx] = u;    int v = son[u];    if (v) top[v] = top[u], dfs2(v);    for (int i = head[u]; i; i = e[i].nxt) {        v = e[i].to;        if (v != fa[u] && v != son[u]) {            top[v] = v;            dfs2(v);        }    }}void dfs(int rt) {//    W[rt] = max(0, w[rt]);    W[rt] = w[rt];    for (int i = head[rt]; i; i = e[i].nxt) {        int v = e[i].to;        if (v != fa[rt]) {            dfs(v);            W[rt] = max(W[rt], W[rt] + W[v]);        }    }}void modify(int x) {    bool o = ST::modify(1, 1, n, dfn[x]);    long long op = ST::ask(dfn[x]);    if (op <= 0) return ;    op *= (o ? 1ll : -1ll);//    printf("op:%lld\n", op);    x = fa[x];    while (x) {        int tmp = ST::query(dfn[top[x]], dfn[x], op);        if (tmp != dfn[top[x]] - 1) {            ST::add(tmp, dfn[x], op);            if (ANS == inf) break;            if (op < 0) {                op = op - ANS;                if (op >= 0) break;            } else {                op = op + ANS;                if (op <= 0) break;            }            x = fa[ret[tmp]];        } else {            ST::add(tmp + 1, dfn[x], op);            x = fa[top[x]];        }    }//    puts("over");}int main() {    scanf("%d%d", &n, &m);    for (int i = 2; i <= n; i++) {        int a;        scanf("%d", &a);        addE(a, i);        addE(i, a);    }    dep[top[1] = 1] = 1;    dfs1(1);    dfs2(1);    for (int i = 1; i <= n; i++) scanf("%lld", w + i);//    for (int i = 1; i <= n; i++) printf("%lld ", dfn[i]); puts("");    dfs(1);    for (int i = 1; i <= n; i++) w[dfn[i]] = W[i];    ST::build(1, 1, n);    while (m --> 0) {        int a;        scanf("%d", &a);        modify(a);        printf("%lld\n", ST::ask(dfn[1]));//        for (int i = 1; i <= n; i++) printf("%lld ", ST::ask(dfn[i])); puts("");    }    return 0;}
     

 

 

 

 

卡点：无

C++ Code：（$100$分）

#include 
     
      #define maxn 100010const long long inf = 0x3f3f3f3f3f3f3f3f;int n, m;long long w[maxn], ANS, now[maxn], sum[maxn];;bool vis[maxn];int head[maxn], cnt;struct Edge {	int to, nxt;} e[maxn << 1];void addE(int a, int b) {	e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}inline long long max(long long a, long long b) {return a > b ? a : b;}inline long long min(long long a, long long b) {return a < b ? a : b;}namespace ST {	struct node {		long long a, b;		node(long long _a = 0, long long _b = 0) {a = _a, b = _b;}		inline node operator + (const node &rhs) {			return (node) {max(a + rhs.a, -inf), max(b + rhs.a, rhs.b)};		}		inline long long mx() {return max(a, b);}	} V[maxn << 2];	inline void update(int rt) {		V[rt] = V[rt << 1 | 1] + V[rt << 1]; //因为右节点深度深，是右节点转移到左节点 	}	int L, R, p;	node num;	void add(int rt, int l, int r) {		if (l == r) {			V[rt] = num;			return ;		}		int mid = l + r >> 1;		if (p > mid) add(rt << 1 | 1, mid + 1, r);		else add(rt << 1, l, mid);		update(rt);	}	void add(int pos, node Num) {		p = pos;		num = Num;		add(1, 1, n);	}	node ask(int rt, int l, int r) {		if (L <= l && R >= r) return V[rt];		int mid = l + r >> 1;		node ans;//		printf("%d %d %d\n", rt, l, r);		if (R > mid) ans = ask(rt << 1 | 1, mid + 1, r);		if (L <= mid) ans = ans + ask(rt << 1, l, mid);		return ans;	}	node ask(int ll, int rr) {		L = ll;		R = rr;//		printf("%d %d\n", L, R);		return ask(1, 1, n);	}}int dfn[maxn], idx, top[maxn], son[maxn], down[maxn];int dep[maxn], fa[maxn], sz[maxn], ret[maxn];void dfs1(int u) {	sz[u] = 1;	for (int i = head[u]; i; i = e[i].nxt) {		int v = e[i].to;		if (v != fa[u]) {			fa[v] = u;			dep[v] = dep[u] + 1;			dfs1(v);			sz[u] += sz[v];			if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;		}	}}void dfs2(int u) {	dfn[u] = ++idx; down[u] = u;	int v = son[u];	if (v) top[v] = top[u], dfs2(v), down[u] = down[v];	for (int i = head[u]; i; i = e[i].nxt) {		v = e[i].to;		if (v != fa[u] && v != son[u]) {			top[v] = v;			dfs2(v);		}	}}void modify(int x) {	long long tmp6 = vis[x] ? -inf : w[x], op = tmp6 - now[x]; now[x] = tmp6;	vis[x] ^= 1;//	printf("op:%lld\n", op);	while (top[x] != 1) {		sum[x] += op;		long long tmp = ST::ask(dfn[top[x]], dfn[down[x]]).mx();		ST::add(dfn[x], ST::node(sum[x]));		tmp = ST::ask(dfn[top[x]], dfn[down[x]]).mx() - tmp;		op = tmp;		x =fa[top[x]];	}	sum[x] += op;	ST::add(dfn[x], ST::node(sum[x])); //	puts("over");}int main() { //	freopen("dark.in", "r", stdin);//	freopen("dark.out", "w", stdout);	scanf("%d%d", &n, &m);	for (int i = 2; i <= n; i++) {		int a;		scanf("%d", &a);		addE(a, i);		addE(i, a);	}	dep[top[1] = 1] = 1;	dfs1(1);	dfs2(1);//	for (int i = 1; i <= n; i++) printf("%lld ", dfn[i]); puts("");//	dfs(1);	for (int i = 1; i <= n; i++) {		scanf("%lld", w + i);		modify(i);		vis[i] = true;	}	while (m --> 0) {		int a;		scanf("%d", &a);		modify(a);		printf("%lld\n", ST::ask(dfn[1], dfn[down[1]]).mx());//		for (int i = 1; i <= n; i++) printf("%lld ", ST::ask(dfn[i])); puts("");	}	return 0;}