constint MAXN = 2005; constint MAXM = MAXN; constint inf = 1 << 29; vector<int> tree[MAXN]; int dp[MAXN][MAXM]; int sz[MAXN]; int n, q, M = 100;
voiddfs(int u){ sz[u] = 1; staticint tmp[MAXN]; for (auto son : tree[u]) { dfs(son); for (int i = 1; i <= min(M, sz[u] + sz[son]); i++) tmp[i] = -inf; for (int i = 1; i <= min(M, sz[u]); i++) { for (int j = 0; j <= min(M - i, sz[son]); j++) { tmp[i + j] = max(tmp[i + j], dp[u][i] + dp[son][j]); } } for (int i = 1; i <= min(M, sz[u] + sz[son]); i++) dp[u][i] = tmp[i]; sz[u] += sz[son]; } }
intmain(){ cin >> n >> q; for (int i = 2; i <= n; i++) { int f; cin >> f; tree[f].push_back(i); } for (int i = 1; i <= n; i++) cin >> dp[i][1]; dfs(1); while (q--) { int u, m; cin >> u >> m; cout << dp[u][m] << endl; } return0; }
int n, m; vector<int> son[N]; vector<array<int, 3>> path[N]; int father[N]; int dep[N];
ll dp[N], sdp[N];
voiddfs(int u){ for (auto v : son[u]) { dfs(v); sdp[u] += dp[v]; } dp[u] = sdp[u]; for (auto p : path[u]) { ll tmp = sdp[u]; int x = p[0]; while (x != u) { tmp += sdp[x] - dp[x]; x = father[x]; } x = p[1]; while (x != u) { tmp += sdp[x] - dp[x]; x = father[x]; } tmp += p[2]; dp[u] = max(dp[u], tmp); } }
intmain(){ cin >> n >> m; for (int i = 2; i <= n; i++) { cin >> father[i]; son[father[i]].push_back(i); dep[i] = dep[father[i]] + 1; // 因为输入是按照顺序的,这里这样也行 } for (int i = 1; i <= m; i++) { int u, v, a; cin >> u >> v >> a; int x = u, y = v; while (x != y) { if (dep[x] > dep[y]) x = father[x]; else y = father[y]; } path[x].push_back({u, v, a}); } dfs(1); cout << dp[1]; return0; }
int n, m; vector<int> son[N]; vector<array<int, 2>> path[N]; int dep[N];
ll dp[N][N];
voidmerge(ll *a, ll *b, int len){ static ll sufa[N], sufb[N]; sufa[len + 1] = inf; sufb[len + 1] = inf; for (int i = len; i >= 1; i--) { sufa[i] = min(sufa[i + 1], a[i]); sufb[i] = min(sufb[i + 1], b[i]); } for (int i = 1; i <= len; i++) { a[i] = min(a[i] + sufb[i], b[i] + sufa[i]); } }
voiddfs(int u){ for (int i = 1; i <= dep[u]; i++) dp[u][i] = inf; for (auto p : path[u]) { dp[u][dep[p[0]]] = min(dp[u][dep[p[0]]], (ll)p[1]); } for (auto v : son[u]) { dfs(v); merge(dp[u], dp[v], dep[v]); } }
intmain(){ cin >> n >> m; dep[1] = 1; for (int i = 2; i <= n; i++) { int f; cin >> f; son[f].push_back(i); dep[i] = dep[f] + 1; // 因为输入是按照顺序的,这里这样也行 } for (int i = 1; i <= m; i++) { int u, v, a; cin >> u >> v >> a; path[v].push_back({u, a}); } dfs(1); if (dp[1][1] >= inf) cout << -1; else cout << dp[1][1]; return0; }