DP on Trees

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Maximum Weighted Independent Set on a Tree
5
// dp[v][1]: best total weight in v's subtree if v is included
6
// dp[v][0]: best total weight in v's subtree if v is excluded
7
8
const int MAXN = 200000;
9
vector<int> g[MAXN + 5];
10
long long w[MAXN + 5];
11
long long dp0[MAXN + 5], dp1[MAXN + 5];
12
13
void dfs(int v, int p) {
14
    dp1[v] = w[v];   // if we include v, start with its weight
15
    dp0[v] = 0;      // if we exclude v, start at 0
16
    for (int u : g[v]) if (u != p) {
17
        dfs(u, v);
18
        // If v is included, children cannot be included
19
        dp1[v] += dp0[u];
20
        // If v is excluded, children can be included or not (take the better)
21
        dp0[v] += max(dp0[u], dp1[u]);
22
    }
23
}
24
25
int main() {
26
    ios::sync_with_stdio(false);
27
    cin.tie(nullptr);
28
29
    int n; 
30
    if (!(cin >> n)) return 0;
31
    for (int i = 1; i <= n; ++i) cin >> w[i];
32
    for (int i = 0; i < n - 1; ++i) {
33
        int u, v; cin >> u >> v;
34
        g[u].push_back(v);
35
        g[v].push_back(u);
36
    }
37
    int root = 1;
38
    dfs(root, 0);
39
    cout << max(dp0[root], dp1[root]) << "\n";
40
    return 0;
41
}
42

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Diameter computed as the maximum sum of top two downward depths at any node
5
6
const int MAXN = 200000;
7
vector<int> g[MAXN + 5];
8
int n;
9
long long diameter_edges = 0;
10
11
int dfs(int v, int p) {
12
    int best1 = -1; // top-1 depth (in edges)
13
    int best2 = -1; // top-2 depth
14
    for (int u : g[v]) if (u != p) {
15
        int d = dfs(u, v); // depth from child u downwards
16
        if (d > best1) { best2 = best1; best1 = d; }
17
        else if (d > best2) { best2 = d; }
18
    }
19
    // depth from v to deepest leaf below is best1 + 1 (if any child), else 0 for leaf
20
    int depth_v = (best1 == -1 ? 0 : best1 + 1);
21
    // Update diameter: if two branches exist, sum them; if one branch, it is best1+1
22
    diameter_edges = max(diameter_edges, 1LL * max(0, best1) + max(0, best2) + 2LL);
23
    if (best1 == -1) diameter_edges = max(diameter_edges, 0LL); // single node case
24
    return depth_v;
25
}
26
27
int main(){
28
    ios::sync_with_stdio(false); cin.tie(nullptr);
29
    cin >> n;
30
    for (int i = 0; i < n - 1; ++i) {
31
        int u, v; cin >> u >> v;
32
        g[u].push_back(v); g[v].push_back(u);
33
    }
34
    // Handle n=1 separately
35
    if (n == 1) { cout << 0 << "\n"; return 0; }
36
    dfs(1, 0);
37
    // The formula above computed two-branch sum in terms of edges; fix exact value:
38
    // Our update added +2 around best1 and best2 which started at -1; simplify by direct formula below
39
    // For clarity, re-run a clean implementation:
40
41
    // Clean implementation for clarity:
42
    diameter_edges = 0;
43
    function<int(int,int)> D = [&](int v, int p){
44
        int best1 = 0, best2 = 0; // depths in edges, 0 for leaf baseline
45
        for (int u : g[v]) if (u != p) {
46
            int d = D(u, v) + 1; // edge to child u
47
            if (d > best1) { best2 = best1; best1 = d; }
48
            else if (d > best2) { best2 = d; }
49
        }
50
        diameter_edges = max(diameter_edges, 1LL * (best1 + best2));
51
        return best1;
52
    };
53
    D(1, 0);
54
    cout << diameter_edges << "\n"; // diameter measured in edges
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count independent sets modulo MOD using multiplicative DP
5
// cnt0[v]: number of valid sets in v's subtree when v is excluded
6
// cnt1[v]: number of valid sets in v's subtree when v is included
7
8
const int MOD = 1'000'000'007;
9
const int MAXN = 200000;
10
vector<int> g[MAXN + 5];
11
long long cnt0[MAXN + 5], cnt1[MAXN + 5];
12
13
void dfs(int v, int p) {
14
    cnt1[v] = 1; // include v: product of cnt0[child]
15
    cnt0[v] = 1; // exclude v: product of (cnt0[child] + cnt1[child])
16
    for (int u : g[v]) if (u != p) {
17
        dfs(u, v);
18
        cnt1[v] = (cnt1[v] * cnt0[u]) % MOD;
19
        long long ways = (cnt0[u] + cnt1[u]) % MOD;
20
        cnt0[v] = (cnt0[v] * ways) % MOD;
21
    }
22
}
23
24
int main(){
25
    ios::sync_with_stdio(false); cin.tie(nullptr);
26
    int n; cin >> n;
27
    for (int i = 0; i < n - 1; ++i) {
28
        int u, v; cin >> u >> v;
29
        g[u].push_back(v); g[v].push_back(u);
30
    }
31
    dfs(1, 0);
32
    cout << (cnt0[1] + cnt1[1]) % MOD << "\n";
33
    return 0;
34
}
35

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute sum of distances from each node to all others using two DFS passes
5
// First pass: compute subtree sizes (sz) and dp[v] = sum of distances from v to its subtree
6
// Second pass: reroot to get ans[u] from ans[v] in O(1) per edge
7
8
const int MAXN = 200000;
9
vector<int> g[MAXN + 5];
10
int n;
11
int sz[MAXN + 5];
12
long long dp[MAXN + 5];
13
long long ansv[MAXN + 5];
14
15
void dfs1(int v, int p){
16
    sz[v] = 1; dp[v] = 0;
17
    for (int u : g[v]) if (u != p) {
18
        dfs1(u, v);
19
        sz[v] += sz[u];
20
        dp[v] += dp[u] + sz[u]; // distance to all nodes in u-subtree increases by 1
21
    }
22
}
23
24
void dfs2(int v, int p){
25
    for (int u : g[v]) if (u != p) {
26
        // Move root from v to u:
27
        // Distances to nodes in u-subtree decrease by 1 (there are sz[u] of them)
28
        // Distances to all other nodes increase by 1 (there are n - sz[u] of them)
29
        ansv[u] = ansv[v] - sz[u] + (n - sz[u]);
30
        dfs2(u, v);
31
    }
32
}
33
34
int main(){
35
    ios::sync_with_stdio(false); cin.tie(nullptr);
36
    cin >> n;
37
    for (int i = 0; i < n - 1; ++i) {
38
        int u, v; cin >> u >> v;
39
        g[u].push_back(v); g[v].push_back(u);
40
    }
41
    int root = 1;
42
    dfs1(root, 0);
43
    ansv[root] = dp[root];
44
    dfs2(root, 0);
45
46
    for (int i = 1; i <= n; ++i) cout << ansv[i] << (i + 1 <= n ? ' ' : '\n');
47
    return 0;
48
}
49