Baltic OI 2017 - Railway

Solution

In this problem, we're given a tree and asked to increment the values of all edges on the spanning trees of $M$ given subsets of nodes.

This is similar to incrementing the values of all edges on given paths, so let's try to adapt the solution for that to this problem. (To increment the values of all edges on a path efficiently, we can use a Fenwick tree.)

We make the following important observation: In a DFS, we traverse each edge exactly twice.

How does this help us? First, we do a DFS on the entire tree and note when each node is visited.

If we sort the chosen nodes $c_i$ in the order that they're visited in the DFS, then the traversal $c_1\to c_2\to \cdots \to c_{s_i}\to c_1$ visits each edge on the spanning tree of the chosen nodes exactly twice.

This means we can split each spanning tree into several paths and increment the values of all edges on those paths individually!

Finally, we check whether the value of each edge is at least $2K$.

The complexity of this algorithm is $\mathcal{O}((S+N)\log N)$.

Code

1#include <bits/stdc++.h>
2using namespace std;
3
4int n, m, k;
5vector<pair<int, int>> graph[100001];
6int tin[100001], tout[100001], timer = 0, anc[100001][20], p_edge[100001];
7int chosen[50001], bit[100001];
8
9void dfs(int node = 1, int parent = 0) {
10    tin[node] = ++timer;