ZZZ's Site

狗蛋儿

3 August 2020

[Codeforces 1389G] Directing Edges

by zzz

Problem Description

Problem Link

Given an undirected connected tree, (N, M <=3e5), directing the tree. Leaving an edge undirected can cost w_i. There are k special nodes. If one node is reachable from all the special nodes, we call it saturated the reward is c_i. For each node i, print the max we can get if node i is for sure saturated.

Solution

Solution from the tutorial

Biconnected Component

Observation 1: in a edge biconnected component, there is a way to direct the edges so every node is in a loop. That means the answer will be the same for nodes in a edge biconnected component.

Undirected Graph:

Edge Biconnected Component: where there is no bridge.
Vertex Biconnected Component: where there is no articulation vertex.
Vetex BCC is for sure Edge BCC, but not vice versa.
If we can see each BCC as a node, a connected undirected graph will be a tree.

Directed Graph:
(Edge) Strongly Connected Component: where there is no bridge

Tree DP

Let’s first fix a root. For each tree(r), calculate the max we can get from the tree(r) where r is saturated. dp[r] = c[r] + sigma(f[v: v is child of r]).

f[v] := dp[v] if tree(v) has no special nodes or has ALL the special nodes, else, max(0, dp[v] - w)

Please note that, the ALL is global ALL, rather than locally in the tree. So, in fact, the dp[r] is the only value that strictly complies the definition and that’s fine.

Rerooting

Let's optimize it to O(n). Root the tree at vertex 1 and calculate the DP as if 1 is the root.
Then, we shall use rerooting technique to recalculate the DP for all other vertices: 
we will try each vertex as the root of the tree, and dp[v] is the answer for the vertex v if it
is the root.

The rerooting technique works as follows:
let's run DFS from the initial root of the tree, and when we traverse an edge by starting or finishing a 
recursive call of DFS, we move the root along the edge; so, if we call DFS(x), x is the current root;
if it has some child y, we move the root to y the same moment when we call DFS(y),
and when the call of DFS(y) ends, the root moves back to x.

Okay, the only thing that's left is to describe how we move the root. If the current root is x, and we
want to move it to y (a vertex adjacent to x), then we have to change only the values of dp[x] and dp[y]

-- from the tutorial.

Looking back

Solving a hard problem earns abundant bonus!

tags: Codeforces - Biconnected Components - Tree DP - Rerooting

Posts

subscribe via RSS