Baltic OI 2017 - Railway

Official Analysis

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 \rightarrow c_2 \rightarrow \dots \rightarrow c_{s_i} \rightarrow 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)$.

Implementation

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

int n, m, k;
vector<pair<int, int>> graph[100001];
int tin[100001], tout[100001], timer = 0, anc[100001][20], p_edge[100001];
int chosen[50001], bit[100001];

void dfs(int node = 1, int parent = 0) {
	tin[node] = ++timer;