Graph
Contest: Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2100
Tags: *special, binary search, dfs and similar, dp, math, ternary search

You are given an undirected graph where each edge has one of two colors: black or red.

Your task is to assign a real number to each node so that:

- for each black edge the sum of values at its endpoints is $$$1$$$;
- for each red edge the sum of values at its endpoints is $$$2$$$;
- the sum of the absolute values of all assigned numbers is the smallest possible.

Otherwise, if it is not possible, report that there is no feasible assignment of the numbers.

Input format:
The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 100\,000$$$) and $$$M$$$ ($$$0 \leq M \leq 200\,000$$$): the number of nodes and the number of edges, respectively. The nodes are numbered by consecutive integers: $$$1, 2, \ldots, N$$$.

The next $$$M$$$ lines describe the edges. Each line contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ denoting that there is an edge between nodes $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq N$$$) with color $$$c$$$ ($$$1$$$ denotes black, $$$2$$$ denotes red).

Output format:
If there is a solution, the first line should contain the word "YES" and the second line should contain $$$N$$$ space-separated numbers. For each $$$i$$$ ($$$1 \le i \le N$$$), the $$$i$$$-th number should be the number assigned to the node $$$i$$$.

Output should be such that:

- the sum of the numbers at the endpoints of each edge differs from the precise value by less than $$$10^{-6}$$$;
- the sum of the absolute values of all assigned numbers differs from the smallest possible by less than $$$10^{-6}$$$.

If there are several valid solutions, output any of them.

If there is no solution, the only line should contain the word "NO".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Scoring:
Subtasks:

1. (5 points) $$$N \leq 5$$$, $$$M \leq 14$$$
2. (12 points) $$$N \leq 100$$$
3. (17 points) $$$N \leq 1000$$$
4. (24 points) $$$N \leq 10\,000$$$
5. (42 points) No further constraints

Note that in the second example the solution is not unique.

Example input:
4 4
1 2 1
2 3 2
1 3 2
3 4 1

Example output:
YES
0.5 0.5 1.5 -0.5

Example input:
2 1
1 2 1

Example output:
YES
0.3 0.7

Editorial:
Subtasks 1-4
These subtasks essentially are for the solutions that have the correct idea (see Subtask 5), but with slower implementation.
Subtask 5
According to the last example in the task statement it is clear that the graph may actually be a multigraph, i.e., may contain more than one edge between a pair of vertices, loops, or isolated vertices.
Reading the input carefully allows us to get rid of extraordinary situations:
• Loops define the values of the vertices (0.5 or 1 depending on the color of the edge).
• For the multi-edges it should be checked that all edges are of the same color. If not, there is no solution.
• For each isolated vertex a 0 should be assigned.
Since there may be several connected components, the task should be solved for each component separately. Minimum sums of absolute values found for separate components will sum up to the minimum sum for the whole graph.
Let's investigate a solution for a single connected component.
For each vertex we will assign a tuple $$$(a, b)$$$ which corresponds to the value in the form $$$ax + b$$$ where $$$a \in \{-1,0,1\}$$$ and $$$b$$$ — any real number. Any vertex may be already processed or not yet processed. Value $$$a=0$$$ means that for the particular vertex the exact value is already known ($$$b$$$). If $$$a \neq 0$$$, it means that we still do not know the exact value for the particular vertex — it still contains a variable part.
We start with an arbitrary vertex $$$v_0$$$ and assign $$$(1,0)$$$ to it. This means that the vertex is processed while the exact value is still unknown (we can denote it by a variable $$$x$$$). Now let's process all other vertices by DFS going from already processed vertices via edges.
Let's see what are the possible cases if an already processed vertex $$$v$$$ is connected with a vertex $$$u$$$.
We first calculate $$$(a_u', b_u')$$$, the values for $$$u$$$ that follow from values for $$$v$$$ and the color of the edge that connects them. Namely, $$$a_u' = -a_v$$$ and $$$b_u' = 1 - b_v$$$ if the edge is black or $$$b_u' = 2 - b_v$$$ if the edge is red.
Then we check whether $$$u$$$ is already processed. If not, we assign $$$(a_u, b_u) = (a_u', b_u')$$$ and proceed with DFS. If, however, the vertex is already processed (we have found a cycle), there are several cases:
• If $$$a_u = a_u'$$$ and $$$b_u = b_u'$$$, there is no additional information and we proceed with DFS.
• If $$$a_u = a_u'$$$ and $$$b_u \neq b_u'$$$, there is contradiction and we can stop DFS.
• Otherwise we have $$$a_u a_v = -1$$$, in which case it is possible to establish the value of $$$x$$$: $$$x_{\mathrm{val}}=(b_v-b_u)/(a_u-a_v)$$$. Now that we know $$$x_{val}$$$ we need to recalculate the values for all the already processed vertices by replacing $$$(a_w, b_w)$$$ with $$$(0, a_w x_{\mathrm{val}} + b_w)$$$.
It can be seen that during the DFS we may need to replace the values for already processed vertices only once, and after that all further processed vertices will have exact values ($$$a_v=0$$$).
If at the end we have $$$a_v=0$$$ for all vertices, this is the only valid solution.
Otherwise ($$$|a_v|=1$$$) we need to find the value of $$$x$$$ giving the overall minimum for the sum of absolute values. Lets take all values of $$$b_v$$$ (for $$$a_v = -1$$$) and $$$-b_v$$$ (for $$$a_v = 1$$$) and find the median of them. It can be proved that this is the value of $$$x$$$ resulting in the overall minimum (proof left as an exercise). To find the median of $$$N$$$ numbers, you can use various algorithms:
• You can sort the numbers and take the middle one ($$$O(N \log N)$$$).
• You can use the quickselect algorithm (expected running time $$$O(N)$$$, $$$O(N^2)$$$ worst-case).
• You can use the median-of-medians algorithm ($$$O(N)$$$ worst-case).
Complexity: $$$O(N + M)$$$ / $$$O(N \log N + M)$$$.