#include<iostream> #include<vector> using namespace std; const int N = 1e5+100; typedef long long ll; vector<int> G[N]; int w[N]; ll dp[N], ans = -1e18; int n; void dfs(int u, int f) { dp[u] = w[u]; for (int v : G[u]) { if (v == f) continue; dfs(v, u); if (dp[v] > 0) { dp[u] += dp[v]; } } ans = max(ans, dp[u]); } int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> w[i]; } int u, v; for (int i = 1; i < n; ++i) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); cout << ans << endl; return 0; }
Java
1
import java.util.*; publicclassMain { privatestaticfinalintN= (int) (1e5 + 100); privatestaticlong[] dp; privatestaticint[] w; privatestatic List<List<Integer>> G; privatestaticlongans= Long.MIN_VALUE; privatestaticint n; privatestaticvoiddfs(int u, int f) { dp[u] = w[u]; for (int v : G.get(u)) { if (v == f) continue; dfs(v, u); if (dp[v] > 0) { dp[u] += dp[v]; } } ans = Math.max(ans, dp[u]); } publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); n = scanner.nextInt(); w = newint[N]; G = newArrayList<>(); for (inti=0; i < N; i++) { G.add(newArrayList<>()); } dp = newlong[N]; for (inti=0; i < n; i++) { w[i] = scanner.nextInt(); } for (inti=0; i < n - 1; i++) { intu= scanner.nextInt() - 1; // 0-indexed in Java int v = scanner.nextInt() - 1; G.get(u).add(v); G.get(v).add(u); } dfs(0, -1); System.out.println(ans); scanner.close(); } }
Python
1
import sys sys.setrecursionlimit(100000) n = int(input()) aList = [0] + [int(i) for i ininput().split()] tree = [[]for i inrange(n+1)] ans = 0 dp = [0for i inrange(n+1)] for i inrange(n-1): m, n =map(int, input().split()) tree[m].append(n) tree[n].append(m) defdfs(u,f): global ans dp[u] = aList[u] for i in tree[u]: if i !=f: dp[i] = dfs(i, u) if dp[i]>0: dp[u] += dp[i] ans=max(ans, dp[u]) return dp[u] dfs(1, 0) print(ans)
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 1e2+20; vector<int> G[N]; int n, V; int v[N], w[N]; int dp[N][N]; void dfs(int u) { for (int i = v[u]; i <= V; ++i) dp[u][i] = w[u]; for (int i : G[u]) { dfs(i); for (int j = V; j >= v[u] + v[i]; --j) { for (int k = v[i]; k <= j - v[u]; ++k) // 剩余的空间 dp[u][j] = max(dp[u][j - k] + dp[i][k], dp[u][j]); } } } int main() { cin >> n >> V; int s; for (int i = 1; i <= n; ++i) { cin >> v[i] >> w[i] >> s; G[s].push_back(i); } dfs(0); cout << dp[0][V] << '\n'; }
Java
1
import java.util.ArrayList; import java.util.List; import java.util.Scanner; publicclassMain { privatestaticint V; privatestaticint[][] dp; privatestatic List<List<Integer>> G; privatestaticint[] v; privatestaticint[] w; privatestaticvoiddfs(int u) { for (inti= v[u]; i <= V; ++i) { dp[u][i] = w[u]; } for (int child : G.get(u)) { dfs(child); for (intj= V; j >= v[u] + v[child]; --j) { for (intk= v[child]; k <= j - v[u]; ++k) { dp[u][j] = Math.max(dp[u][j - k] + dp[child][k], dp[u][j]); } } } } publicstaticvoidmain(String[] args) { Scannerscanner=newScanner(System.in); intn= scanner.nextInt(); V = scanner.nextInt(); G = newArrayList<>(); for (inti=0; i <= n; ++i) { G.add(newArrayList<>()); } v = newint[n + 1]; w = newint[n + 1]; dp = newint[n + 1][V + 1]; for (inti=1; i <= n; ++i) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); ints= scanner.nextInt(); G.get(s).add(i); } dfs(0); System.out.println(dp[0][V]); scanner.close(); } }
Python
1
classSolution: defdfs(self, u, dp, G, v, w, V): for i inrange(v[u], V + 1): dp[u][i] = w[u] for child in G[u]: self.dfs(child, dp, G, v, w, V) for j inrange(V, v[u] + v[child] - 1, -1): for k inrange(v[child], j - v[u] + 1): dp[u][j] = max(dp[u][j - k] + dp[child][k], dp[u][j]) defmain(self): n, V = map(int, input().split()) G = [[] for _ inrange(n + 1)] # 0-indexed in Python v = [0] * (n + 1) w = [0] * (n + 1) for i in range(1, n + 1): v[i], w[i], s = map(int, input().split()) G[s].append(i) dp = [[0] * (V + 1) for _ in range(n + 1)] self.dfs(0, dp, G, v, w, V) print(dp[0][V]) # Run the main function solution = Solution() solution.main()
voiddfs(int u, int f, int dt){ // 求出以1为根的原始信息 dep[u] = dt; Mdp[u] = 0; // Mdp即为当前点为根的最大深度 for (int v : G[u]) { if (v == f) continue; dfs(v, u, dt + 1); Mdp[u] = max(Mdp[v] + 1, Mdp[u]); } }
#include<iostream> #include<vector> using namespace std; const int N = 1e5+10; vector<int> G[N]; int n, k, c; int dep[N], Mdp[N]; typedef long long ll; ll ans = 0; void dfs(int u, int f, int dt) { // 求出以1为根的原始信息 dep[u] = dt; Mdp[u] = 0; for (int v : G[u]) { if (v == f) continue; dfs(v, u, dt + 1); Mdp[u] = max(Mdp[v] + 1, Mdp[u]); } } void dfs2(int u, int f) { // 开始换根 /** * 重新转移 */ int tmpf = 0, Mx1 = 0, Mx2 = 0; for (int v : G[u]) { tmpf = max(tmpf, Mdp[v] + 1); } // 维护答案 ans = max(1ll * tmpf * k - 1ll * dep[u] * c, ans); // 根变儿子步骤 int pre = Mdp[u]; for (int v : G[u]) { if (Mdp[v] + 1 > Mx1) { Mx2 = Mx1; Mx1 = Mdp[v] + 1; } else if (Mdp[v] + 1 > Mx2) { Mx2 = Mdp[v] + 1; } } for (int v : G[u]) { if (v == f) continue; // 由于根要变成儿子,所以要改变原来的转移值 if (Mdp[v] + 1 == Mx1) Mdp[u] = Mx2; else Mdp[u] = Mx1; dfs2(v, u); } // 还原原始的值。 Mdp[u] = pre; } void sol() { for (int i = 1; i <= n; ++i) G[i].clear(); ans = 0; cin >> n >> k >> c; int u, v; for (int i = 1; i < n; ++i) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1, 0, 0); dfs2(1, 0); cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); int T; cin >> T; while (T --) { sol(); } return 0; }
Python
1
from collections import defaultdict import sys sys.setrecursionlimit(100000) N = 100010 G = defaultdict(list) n, k, c = 0, 0, 0 dep = [0] * N Mdp = [0] * N ans = 0defdfs(u, f, dt): # 求出以1为根的原始信息 global dep, Mdp dep[u] = dt Mdp[u] = 0 for v in G[u]: if v == f: continue dfs(v, u, dt + 1) Mdp[u] = max(Mdp[v] + 1, Mdp[u]) def dfs2(u, f): # 开始换根 global ans, dep, Mdp tmpf = 0 Mx1 = 0 Mx2 = 0 # 重新转移 for v in G[u]: tmpf = max(tmpf, Mdp[v] + 1) # 维护答案 ans = max(ans, tmpf * k - dep[u] * c) # 根变儿子步骤 pre = Mdp[u] for v in G[u]: if Mdp[v] + 1 > Mx1: Mx2 = Mx1 Mx1 = Mdp[v] + 1 elif Mdp[v] + 1 > Mx2: Mx2 = Mdp[v] + 1 for v in G[u]: if v == f: continue # 由于根要变成儿子,所以要改变原来的转移值 if Mdp[v] + 1 == Mx1: Mdp[u] = Mx2 else: Mdp[u] = Mx1 dfs2(v, u) # 还原原始的值。 Mdp[u] = pre def sol(): global n, k, c, ans, G, dep, Mdp n, k, c = map(int, input().split()) G.clear() ans = 0 for _ in range(n - 1): u, v = map(int, input().split()) G[u].append(v) G[v].append(u) dfs(1, 0, 0) dfs2(1, 0) print(ans) T = int(input()) for _ in range(T): sol()
Java
1
import java.util.*; import java.io.*; publicclassMain { staticfinalintN=100010; static List<Integer>[] G; staticint n, k, c; staticint[] dep, Mdp; staticlong ans; staticvoiddfs(int u, int f, int dt) { // 求出以1为根的原始信息 Mdp[u] = 0; for (int v : G[u]) { if (v == f) continue; dfs(v, u, dt + 1); Mdp[u] = Math.max(Mdp[v] + 1, Mdp[u]); } } static void dfs2(int u, int f) { // 开始换根 int tmpf = 0, Mx1 = 0, Mx2 = 0; /** * 重新转移 */ for (int v : G[u]) { tmpf = Math.max(tmpf, Mdp[v] + 1); } // 维护答案 ans = Math.max(ans, (long) tmpf * k - (long) dep[u] * c); // 根变儿子步骤 int pre = Mdp[u]; for (int v : G[u]) { if (Mdp[v] + 1 > Mx1) { Mx2 = Mx1; Mx1 = Mdp[v] + 1; } else if (Mdp[v] + 1 > Mx2) { Mx2 = Mdp[v] + 1; } } for (int v : G[u]) { if (v == f) continue; // 由于根要变成儿子,所以要改变原来的转移值 if (Mdp[v] + 1 == Mx1) { Mdp[u] = Mx2; } else { Mdp[u] = Mx1; } dfs2(v, u); } // 还原原始的值。 Mdp[u] = pre; } static void sol(Scanner scanner) { for (int i = 1; i <= n; i++) G[i].clear(); ans = 0; n = scanner.nextInt(); k = scanner.nextInt(); c = scanner.nextInt(); int u, v; for (int i = 1; i < n; i++) { u = scanner.nextInt(); v = scanner.nextInt(); G[u].add(v); G[v].add(u); } dfs(1, 0, 0); dfs2(1, 0); System.out.println(ans); } public static void main(String[] args) { G = new ArrayList[N]; for (int i = 0; i < N; i++) { G[i] = new ArrayList<>(); } dep = new int[N]; Mdp = new int[N]; Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); while (T-- > 0) { sol(scanner); } } }