MOODLECT - Editorial

Contest:

Summer of innovation

Problem:

Moodle Chat

Topics:

DP on trees + (Binary Lifting/ Square root Decomposition)

Solution:

subtask details:

  1. Free marks for every one who can write entry level code (basic input output)
  2. Marks for those who can implement brute force solution (finding subtree in O(n) and summing up the corresponding values of nodes in subtree)
  3. Marks for those who can figure out the standard dp based approach to sum values of subtree O(1) per query. This also gives hint to try finding the lca in better time complexity.
  4. Precompute the parent nodes in given tree, so that we can find Lowest common ancestor in O(logn) using Binary Lifting. Run a dfs on the given tree and for each node i, store sum of values of all nodes in the subtree rooted at the current node, say this value b[i]. For each query, we have to print the value of b[lca(u, v)], as the subtree rooted at lca(u, v) will be the smallest.
    Thus we answer in O(logn) per query.

P.S. N and q are <= 105, can you think of some solution in O(q * sqrt(n)) ?

Find other accepted solutions here

One possible implementation:

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define pi pair<ll,ll>

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int lg = log2(N) + 1;

vector<vector<int>> tree, parent(N, vector<int> (lg, 0));
vector<ll> depth(N, 0), values, dp;
int n, q;

bool isSet(int bit, int num) {
    return num & (1 << bit);
}

// pre-calculation step, parent[node][i] stores the power(2, i)th parent of 'node'
void dfs(int node, int par = 0, int height = 0) {
    parent[node][0] = par;
    depth[node] = height;
    for (int i = 1; i < parent[node].size(); i += 1) {
        int var = parent[node][i-1];
        parent[node][i] = parent[var][i-1];
    }

    for (auto child: tree[node]) {
        if (child != par)
            dfs(child, node, height+1);
    }
}

int lca(int node1, int node2) {
    if (depth[node2] > depth[node1])
        swap(node1, node2);
    // now depth[node1] >= depth[node2]
    int dist = depth[node1] - depth[node2];

    // Jump node1 upwards until depth[node1] != depth[node2]
    // consider the binary form of 'dist' for better understanding
    for (int i = 31; i >= 0; i -= 1) {
        if (isSet(i, dist)) {
            node1 = parent[node1][i];
        }
    }

    if (node1 == node2)
        return node1;
    else if (node1 == 1 || node2 == 1)
        return 1;

    // now node2 and node1 are on the same level
    // While they both don't share same parent, keep jumping up
    // note we are iterating from 31-1 and not from 1-31
    // the former gives log(n) time while the later O(n)
    // Again consider the binary form of depth[lca] - depth[node1] for understanding
    for (int i = lg-1; i >= 0; i -= 1) {
        if (parent[node1][i] == parent[node2][i])
            continue;
        node1 = parent[node1][i];
        node2 = parent[node2][i];
    }

    return parent[node1][0];
}

void dfs_dp(int node, int par = 0) {
	dp[node] = values[node];

	for (auto child: tree[node]) {
		if (child == par)
			continue;
		dfs_dp(child, node);
		dp[node] = (dp[node] + dp[child]) % mod;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	cin >> n;
    tree.resize(n+2);

    for (int i = 1; i < n; i += 1) {
        int u, v;   cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(1);

    // cout << "Precomputation complete\n";

    values = vector<ll> (n+1, 0);
    dp = vector<ll> (n+1, 0);
    for (int i = 1; i <= n; i += 1)
    	cin >> values[i];

    dfs_dp(1);

    // cout << "DP complete\n";
    cin >> q;

    while (q--) {
    	int u, v;	cin >> u >> v;
    	// cout << "for (" << u << ',' << v << "), lca is: " << lca(u, v) << ' ';
    	cout << dp[lca(u, v)] << '\n';
    }


	return 0;
}

Please give access for practice submission to all of the problems

Hi. It would take some time to move the problems to practice section. You could expect the submission to be active by tomorrow.