CF533B(树形dp+转移技巧)

题意：
有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？

思路:

显然是用树形dp解决,假设f(i, 1/0)为以i为根的子树的最大权值.此时考虑转移,

初始化f(i, 0) = 0, f(i, 1) = -INF,表示当前这棵子树还没选i这个点.对于转移,我自己是这么想的,枚举每个点选奇数还是选偶数,但是会爆时间.我们可以再套个dp进行转移.假设u -> v

f(u, 0) = max(f(u, 0) + f(v, 0), f(u, 1) + f(v, 1)) 偶 + 偶 = 奇 + 奇 = 偶

f(u, 1) = max(f(u, 1) + f(v, 0), f(u, 0) + f(v, 1)) 偶 + 奇 = 奇 + 偶 = 奇

代码:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
#define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x)) 
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f 
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e5 + 10;
int n, a[N], f[N][2], root;
vector<int> son[N];
//f[i][1/0]表示以i为根的子树中职员有奇数个/偶数个的最大权值
void dfs(int x, int fa) {
	f[x][1] = -INF, f[x][0] = 0;
	for (int y : son[x]) {
		if (y == fa) continue;
		dfs(y, x);
		int x0 = f[x][0], x1 = f[x][1];
		f[x][0] = max(f[y][1] + x1, f[y][0] + x0);
		f[x][1] = max(f[y][0] + x1, f[y][1] + x0);
	}
	f[x][1] = max(f[x][1], f[x][0] + a[x]);
}
void solve() { 
	qio >> n;
	for (int i = 1, x; i <= n; ++i) {
		qio >> x >> a[i];
		if (x == -1)
			root = i;
		else {
			son[x].emplace_back(i);
			son[i].emplace_back(x);
		}
	}
	dfs(root, -1);
	qio << max(f[root][1], f[root][2]) << "\n";
}
signed main() {
	int T = 1;
	while (T--) solve();
}