题面

清橙

Sol

一种新的树上\(DP\)姿势

从左往右按链\(DP\)

做法：

维护两个栈\(S1\)，\(S2\)

\(S1\)存当前的链

\(S2\)存分叉点以下要改的链

\(Dfs\)，弄一个分叉点，之前的链经过它，并且另一条要转移到的链也经过它

那么每次在叶节点时就把\(S1\)最下面的一部分变成\(S2\)

转移

两种情况：

最大值在\(S1\)和在\(S2\)的情况

那么枚举\(S2\)，\(S1\)中小于\(S2\)的枚举的值的点就可以转移，并维护\(S1\)，\(S2\)的前缀最大值

再枚举\(S2\)，利用前缀最大值，\(S1\)的大于等于\(S2\)的转移

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

# define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

using namespace std;

typedef long long ll;

const int _(1e5 + 5);

IL int Input(){

    RG int x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, val[_], f[_], ans = -2e9;

int fa[_], S1[_], S2[_], id[_], maxv[_];

vector <int> edge[_];

IL void Dfs(RG int u, RG int top){   //top是分叉点在S1中的位置

	if(!top) S1[++S1[0]] = u, id[u] = S1[0], f[u] = val[u]; //初始第一条链

	RG int l = edge[u].size();

	if(l){    //非叶子节点不做更新

		for(RG int i = 0; i < l; ++i){

			RG int v = edge[u][i];

			if(!i){   //最左边的直接加入S2

				if(top) S2[++S2[0]] = v;

				Dfs(v, top);

			}

			else S2[S2[0] = 1] = v, Dfs(v, id[u]); //新开一条链

		}

		return;

	}

	if(!top) return;

	RG int mx1 = val[S1[top]], maxf = ans, now = top, mx2 = mx1;

	for(RG int i = 1; i <= S2[0]; ++i){  //最大值在S2中的情况

		while(now < S1[0] && val[S1[now]] <= mx1){ //计算每个最大值的贡献

			mx2 = max(mx2, val[S1[now]]);

			maxf = max(maxf, f[S1[++now]]);

			maxv[S1[now]] = mx2;  //维护S1前缀最大值

		}

		f[S2[i]] = maxf - mx1;  //转移

		maxv[S2[i]] = mx1;  //维护S2前缀最大值

		mx1 = max(mx1, val[S2[i]]);   //下一个点

	}

	while(now < S1[0]){ //处理剩下的

		mx2 = max(mx2, val[S1[now]]);

		maxv[S1[++now]] = mx2;

	}

	maxf = ans, now = S1[0];

	for(RG int i = S2[0]; i; --i){ //最大值在S1中的情况

		while(now > top && maxv[S1[now]] >= maxv[S2[i]]){

			maxf = max(maxf, f[S1[now]] - maxv[S1[now]]);

			--now;

		}

		f[S2[i]] = max(f[S2[i]], maxf);

	}

	for(RG int i = 1; i <= S2[0]; ++i){ //更新到下一条链

		f[S2[i]] += val[S2[i]];

		S1[top + i] = S2[i];

		id[S2[i]] = top + i;

	}

	S1[0] = top + S2[0];

}

int main(RG int argc, RG char* argv[]){

	File("cut");

	n = Input(), Fill(f, -127);

	for(RG int i = 1, t; i <= n; ++i){

		val[i] = Input(), t = Input();

		for(RG int j = 1, tt; j <= t; ++j)

			tt = Input(), edge[i].push_back(tt);

	}

	Dfs(1, 0);

	for(RG int i = 1; i <= S1[0]; ++i) ans = max(ans, f[S1[i]]);

	printf("%d\n", ans);

    return 0;

}