homework_detail - 蒙青创OJ

/*
树上DP
1.选点

f[x][0]x点不去的最大价值 f[x][0]+=max(f[v][0],f[v][1])
f[x][1]x点去的最大价值   f[x][1]+=f[v][0]
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 6005;
int n, f[N][2], a[N];
vector<int>e[N];
void dfs(int x, int fa) {
	f[x][0] = 0;
	f[x][1] = a[x];
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		f[x][0] += max(f[v][0], f[v][1]);
		f[x][1] += f[v][0];
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	cout << max(f[1][0], f[1][1]) << endl;
	return 0;
}

/*
一共选m节课
f[x][k]以x为根的子树，选k节课的最大价值
f[x][k] = f[v][s]+f[x][k-s]

*/
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n, m, a[N], f[N][N];
vector<int>e[N];
void dfs(int x, int fa) {
	f[x][1] = a[x];
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		//枚举以x为根的子树，选的节点的个数
		for (int i = m; i >= 1; i--) {
			//枚举在v上，选多少个节点
			for (int j = i - 1; j >= 0; j--) {
				f[x][i] = max(f[x][i], f[v][j] + f[x][i - j]);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	m++;
	for (int i = 1; i <= n; i++) {
		int fa;
		cin >> fa >> a[i];
		e[fa].push_back(i);
		e[i].push_back(fa);
	}
	dfs(0, -1);
	cout << f[0][m] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 16005;
int n, m, f[N], a[N];
vector<int>e[N];

void dfs(int x, int fa) {
	f[x] = a[x];
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		if (f[v] >= 0)
			f[x] += f[v];
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	int res = -1e9;
	for (int i = 1; i <= n; i++) {
		res = max(res, f[i]);
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, f[N][N];

struct node {
	int v, w;
};
vector<node>e[N];

void dfs(int x, int fa) {
	for (auto [v, w] : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		for (int j = m; j >= 1; j--) {
			for (int k = j - 1; k >= 0; k--) {
				f[x][j] = max(f[x][j], f[v][k] + f[x][j - k - 1] + w);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs(1, 0);
	cout << f[1][m] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, siz[N], f[N], dep[N];
vector<int>e[N];

void dfs(int x, int fa, int deep) {
	dep[x] = deep;
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x, deep + 1);
		siz[x] += siz[v];
	}
}

void dfs2(int x, int fa) {
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		f[v] = f[x] + n - 2 * siz[v];
		dfs2(v, x);
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0, 1);
	for (int i = 1; i <= n; i++) {
		f[1] += dep[i];
	}
	dfs2(1, 0);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (f[res] < f[i]) {
			res = i;
		}
	}
	cout << res << endl;
	return 0;
}

/*
f[x]x到最长的叶子需要花费的时间
g[v] += f[x]-f[v]-w
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, s, res, f[N];

struct node {
	int v, w;
};
vector<node>e[N];

void dfs(int x, int fa) {
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == fa)
			continue;
		dfs(v, x);
		if (f[v] + w > f[x]) {
			f[x] = f[v] + w;
		}
	}

	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == fa)
			continue;
		res += f[x] - f[v] - w;
	}

}

signed main() {
	cin >> n >> s;
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs(s, 0);
	cout << res << endl;
	return 0;
}

/*
f[x][0]x的子树和x的父亲都被信号覆盖
f[x][0] = 1+f[v][2]

f[x][1]x及x的子树的子树被信号覆盖
f[x][1] += f[v][0]+f[t][1]

f[x][2]x的子树不包括x被信号覆盖
f[x][2] = f[v][1]
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, f[N][5];
vector<int>e[N];

void dfs(int x, int fa) {
	f[x][0] = 1;
	f[x][1] = 1e9;
	int son = 0, sum = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i];
		if (v == fa)
			continue;
		son++;
		dfs(v, x);
		f[x][0] += f[v][2];
		f[x][2] += f[v][1];
		sum += f[v][1];
	}
	if (son == 0) {
		f[x][0] = f[x][1] = 1;
	}
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i];
		if (v == fa)
			continue;
		f[x][1] = min(f[x][1], f[v][0] + sum - f[v][1]);
	}
	for(int i=1;i<=2;i++){
		f[x][i] = min(f[x][i],f[x][i-1]);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	cout << f[1][1] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, f[N][10];
vector<int>e[N];

void dfs(int x, int fa) {
	f[x][0] = 1;
	f[x][1] = f[x][2] = 1e9;
	int sum2 = 0, sum3 = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i];
		if (v == fa)
			continue;
		dfs(v, x);
		f[x][0] += f[v][4];
		sum2 += f[v][2];
		sum3 += f[v][3];
		f[x][3] += f[v][2];
		f[x][4] += f[v][3];
	}
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i];
		if (v == fa)
			continue;
		f[x][1] = min(f[x][1], f[v][0] + (sum3 - f[v][3]));
		f[x][2] = min(f[x][2], f[v][1] + (sum2 - f[v][2]));
	}
	for (int i = 1; i <= 4; i++) {
		f[x][i] = min(f[x][i], f[x][i - 1]);
	}
}

int main() {
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		e[i].push_back(x);
		e[x].push_back(i);
	}
	dfs(1, 0);
	cout << f[1][2] << endl;
	return 0;
}

/*
f[x][0]将x染色成0号颜色的方法总数
f[x][0] = f[v][1]+f[v][2]
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10, Mod = 1e9 + 7;
int n, m, a[N], f[N][5];
vector<int>e[N];

void dfs(int x, int fa) {
	if (a[x] != -1) {
		f[x][a[x]] = 1;
	} else {
		f[x][0] = f[x][1] = f[x][2] = 1;
	}
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		f[x][0] *= (f[v][1] + f[v][2]) % Mod;
		f[x][0]%=Mod;
		f[x][1] *= (f[v][0] + f[v][2]) % Mod;
		f[x][1]%=Mod;
		f[x][2] *= (f[v][0] + f[v][1]) % Mod;
		f[x][2]%=Mod;
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	memset(a, -1, sizeof(a));
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		y--;
		a[x] = y;
	}
	dfs(1, 0);
	cout << ((f[1][0] + f[1][1]) % Mod + f[1][2]) % Mod << endl;
	return 0;
}

/*
f[x][j]以x为根的子树，剩余j个节点，最少删除的边数
f[x][j] = min(f[x][j],f[v][k]+f[x][j-k])

f[x][j]+1
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 155;
int n, p, siz[N], f[N][N];
vector<int>e[N];
void dfs(int x, int fa) {
	siz[x] = 1;
	f[x][1] = 0;
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		siz[x] += siz[v];
		for (int i = siz[x]; i >= 0; i--) {
			f[x][i]++;
			for (int j = 0; j <= siz[v]; j++) {
				f[x][i] = min(f[x][i], f[v][j] + f[x][i - j]);
			}
		}
	}
}

int main() {
	cin >> n >> p;
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	int res = 1e9;
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			res = min(res, f[i][p]);
		else
			res = min(res, f[i][p] + 1);
	}
	cout << res << endl;
	return 0;
}

/*
f[x][j] = min(f[x][j],f[v][k]+f[x][j-k]+val)
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int siz[N], n, m, f[N][N];

struct node {
	int v, w;
};
vector<node>e[N];

void dfs(int x, int fa) {
	siz[x] = 1;
	for (auto [v, w] : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		siz[x] += siz[v];
		for (int j = min(m, siz[x]); j >= 0; j--) {
			for (int k = max(0LL,j-siz[x]+siz[v]); k <= min(siz[v], j); k++) {
				int val = w * (k * (m - k)) + w * (siz[v] - k) * (n - m - siz[v] + k);
				f[x][j] = max(f[x][j], f[v][k] + f[x][j - k] + val);
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	m = min(m, n - m);
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs(1, 0);
	cout << f[1][m] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
#define int long long
int n, fa[N], a[N], f[N][2], vis[N], incircle[N], g[N][2];
vector<int>e[N];

void dfs(int x) {
	vis[x] = 1;
	f[x][0] = 0;
	f[x][1] = a[x];
	for (auto v : e[x]) {
		if (incircle[v])
			continue;
		dfs(v);
		f[x][0] += max(f[v][0], f[v][1]);
		f[x][1] += f[v][0];
	}
}

signed main() {
	cin >> n;
	int res = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> fa[i];
		e[fa[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0) {
			int u = i;
			while (vis[u] == 0) {
				vis[u] = 1;
				u = fa[u];
			}
			vector<int>circle;
			int v = fa[u];
			while (v != u) {
				circle.push_back(v);
				incircle[v] = 1;
				v = fa[v];
			}
			incircle[u] = 1;
			circle.push_back(u);
		//	reverse(circle.begin(), circle.end());
			for (auto v : circle) {
				dfs(v);
			}
			int tmp = 0;
			for (int t = 0; t <= 1; t++) {
				//t=0 circle[0]不选
				if (t == 0) {
					g[0][0] = f[circle[0]][0];
					g[0][1] = 0;
				} else {
					g[0][0] = 0;
					g[0][1] = f[circle[0]][1];
				}
				for (int i = 1; i < circle.size() - 1; i++) {
					g[i][0] = f[circle[i]][0] + max(g[i - 1][0], g[i - 1][1]);
					g[i][1] = f[circle[i]][1] + g[i - 1][0];
				}
				if (t == 0) {
					int x = circle.size() - 1;
					g[x][0] = f[circle[x]][0] + max(g[x - 1][0], g[x - 1][1]);
					g[x][1] = f[circle[x]][1] + g[x - 1][0];
				} else {
					int x = circle.size() - 1;
					g[x][0] = f[circle[x]][0] + max(g[x - 1][0], g[x - 1][1]);
					g[x][1] = 0;
				}
				int x = circle.size() - 1;
				tmp = max(tmp, max(g[x][0], g[x][1]));
			}
			res += tmp;
		}
		
	}
	cout << res << endl;
	return 0;
}

Please claim the assignment to see the problems.

Status: Live...
Problem: 22
Open Since: 2025-10-1 0:00
Deadline: 2026-1-31 23:59
Extension: 24 hour(s)

Homework Introduction

Problem

SIGN IN