Official Analysis

Explanation

Constraint Propagation

Suppose the value of one endpoint of an edge is $u$. If $u + v = s$, then we can find the value of the other endpoint to be $v = s - u$. Based on this, if we fix one node's value in a connected component, all other values in that component are determined by following the edges.

Determining General Values of Nodes

For each connected component, we can express all node values in terms of a single variable $x$:

• We start with an arbitrary node and set its value to $x$
• Then we propagate through the edges. If $u = ax + b$ and edge $(u,v)$ has sum $s$, then $v = s - u = -ax + (s - b)$

This means that every node's value is represented in the form of $cx + d$, where $c=\pm1$.

Checking Feasibility in Cyclic Connected Components

We encounter a cycle when we visit an already-visited node. This means that we need to check for feasibility.

• If we reach node $u$ again, we have two expressions for it
• The cycle gives us an equation in terms of $x$
• If the equation has no solution or contradicts a previous solution, the problem is infeasible

Acyclic Connected Components

When no cycle determines $x$, we must choose its value to minimize the expression: $\sum_{i=1}^n |a_i x + b_i|$. This can be done by setting $x$ to the median of the roots, as this problem reduces down to the minimization of the sum of absolute differences.

Determining Actual Values of Nodes

Regardless of how we computed $x$, once we have it, we need to propagate this value throughout the connected components. We can plug $x$ into each $ax + b$ and determine the exact value of each node that minimizes the sum of their absolute values.

Implementation

Time Complexity: $\mathcal{O}(N\log N + M)$

Copy
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const ll INF = 1e18;

Copy
import java.io.*;
import java.util.*;

public class Graph {
	static final long INF = (long)1e18;

	static List<List<Pair>> adj;
	static List<Pair> coeffs;  // node value represented as ax + b (stored as {a, b})
	static boolean[] vis;
	static double[] ans;