D. Weighting a Tree

Codeforces

IDCF901D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

You are given a connected undirected graph with _n_ vertices and _m_ edges. The vertices are enumerated from 1 to _n_. You are given _n_ integers _c_1, _c_2, ..., _c__n_, each of them is between - _n_ and _n_, inclusive. It is also guaranteed that the parity of _c__v_ equals the parity of degree of vertex _v_. The degree of a vertex is the number of edges connected to it. You are to write a weight between - 2·_n_2 and 2·_n_2 (inclusive) on each edge in such a way, that for each vertex _v_ the sum of weights on edges connected to this vertex is equal to _c__v_, or determine that this is impossible. ## Input The first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 105, _n_ - 1 ≤ _m_ ≤ 105) — the number of vertices and the number of edges. The next line contains _n_ integers _c_1, _c_2, ..., _c__n_ ( - _n_ ≤ _c__i_ ≤ _n_), where _c__i_ is the required sum of weights of edges connected to vertex _i_. It is guaranteed that the parity of _c__i_ equals the parity of degree of vertex _i_. The next _m_ lines describe edges of the graph. The _i_\-th of these lines contains two integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_; _a__i_ ≠ _b__i_), meaning that the _i_\-th edge connects vertices _a__i_ and _b__i_. It is guaranteed that the given graph is connected and does not contain loops and multiple edges. ## Output If there is no solution, print "_NO_". Otherwise print "_YES_" and then _m_ lines, the _i_\-th of them is the weight of the _i_\-th edge _w__i_ ( - 2·_n_2 ≤ _w__i_ ≤ 2·_n_2). [samples]

你被给定一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通无向图。顶点编号从 #cf_span[1] 到 #cf_span[n]。你被给定 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]，每个整数介于 #cf_span[ - n] 和 #cf_span[n] 之间（包含两端）。同时保证 #cf_span[cv] 的奇偶性与顶点 #cf_span[v] 的度数的奇偶性相同。顶点的度数是指与其相连的边的数量。你需要在每条边上写一个介于 #cf_span[ - 2·n2] 和 #cf_span[2·n2] 之间（包含两端）的权重，使得对于每个顶点 #cf_span[v]，与其相连的所有边的权重之和等于 #cf_span[cv]；如果不可能，则判定为无解。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[n - 1 ≤ m ≤ 105]）——顶点数和边数。下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[ - n ≤ ci ≤ n]），其中 #cf_span[ci] 是顶点 #cf_span[i] 所连边的权重之和的期望值。保证 #cf_span[ci] 的奇偶性与顶点 #cf_span[i] 的度数的奇偶性相同。接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示第 #cf_span[i] 条边连接顶点 #cf_span[ai] 和 #cf_span[bi]。保证给定的图是连通的，且不包含自环和重边。如果无解，请输出 "_NO_"。否则输出 "_YES_"，然后输出 #cf_span[m] 行，第 #cf_span[i] 行为第 #cf_span[i] 条边的权重 #cf_span[wi]（#cf_span[ - 2·n2 ≤ wi ≤ 2·n2]）。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[n - 1 ≤ m ≤ 105]）——顶点数和边数。下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[ - n ≤ ci ≤ n]），其中 #cf_span[ci] 是顶点 #cf_span[i] 所连边的权重之和的期望值。保证 #cf_span[ci] 的奇偶性与顶点 #cf_span[i] 的度数的奇偶性相同。接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示第 #cf_span[i] 条边连接顶点 #cf_span[ai] 和 #cf_span[bi]。保证给定的图是连通的，且不包含自环和重边。 ## Output 如果无解，请输出 "_NO_"。否则输出 "_YES_"，然后输出 #cf_span[m] 行，第 #cf_span[i] 行为第 #cf_span[i] 条边的权重 #cf_span[wi]（#cf_span[ - 2·n2 ≤ wi ≤ 2·n2]）。 [samples]

**Definitions** Let $ G = (V, E) $ be a connected undirected graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \{1, 2, \dots, n\} $. Let $ d_v $ denote the degree of vertex $ v \in V $. Let $ c_v \in \mathbb{Z} $ be the required sum of edge weights incident to vertex $ v $, with $ -n \leq c_v \leq n $ and $ c_v \equiv d_v \pmod{2} $ for all $ v \in V $. Let $ w_e \in \mathbb{Z} $ be the weight assigned to edge $ e \in E $, with $ -2n^2 \leq w_e \leq 2n^2 $. **Constraints** 1. $ 2 \leq n \leq 10^5 $, $ n - 1 \leq m \leq 10^5 $ 2. $ \sum_{v \in V} c_v $ is even (implicit from handshaking lemma and parity condition) 3. For each vertex $ v \in V $: $$ \sum_{e \in \delta(v)} w_e = c_v $$ where $ \delta(v) $ is the set of edges incident to $ v $. **Objective** Determine whether there exists an assignment of weights $ \{w_e\}_{e \in E} $ satisfying the above constraints. If yes, output such an assignment; otherwise output "NO".

Samples

Input #1

Output #1

YES
1
1
1

Input #2

Output #2

YES
-1
1
1

Input #3

6 6
3 5 5 5 1 5
1 4
3 2
4 3
4 5
3 5
5 6

Output #3

YES
3
5
3
-1
-3
5

Input #4

Output #4

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Weighting a Tree",
    "description": {
      "content": "You are given a connected undirected graph with _n_ vertices and _m_ edges. The vertices are enumerated from 1 to _n_. You are given _n_ integers _c_1, _c_2, ..., _c__n_, each of them is between  - _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF901D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a connected undirected graph with _n_ vertices and _m_ edges. The vertices are enumerated from 1 to _n_.\n\nYou are given _n_ integers _c_1, _c_2, ..., _c__n_, each of them is between  - _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通无向图。顶点编号从 #cf_span[1] 到 #cf_span[n]。\n\n你被给定 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]，每个整数介于 #cf_span[ - n] 和 #cf_span[n] 之间（包含两端）。同时保证 #cf_span[cv] 的奇偶性与顶点 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \\{1, 2, \\dots, n\\} $.  \nLet $ d_v $ denote the degree of vertex $ v \\i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments