F. Imbalance Value of a Tree

Codeforces

IDCF915F

Time4000ms

Memory256MB

Difficulty—

data structuresdsugraphstrees

English · Original

Chinese · Translation

Formal · Original

You are given a tree _T_ consisting of _n_ vertices. A number is written on each vertex; the number written on vertex _i_ is _a__i_. Let's denote the function _I_(_x_, _y_) as the difference between maximum and minimum value of _a__i_ on a simple path connecting vertices _x_ and _y_. Your task is to calculate . ## Input The first line contains one integer number _n_ (1 ≤ _n_ ≤ 106) — the number of vertices in the tree. The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the numbers written on the vertices. Then _n_ - 1 lines follow. Each line contains two integers _x_ and _y_ denoting an edge connecting vertex _x_ and vertex _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_). It is guaranteed that these edges denote a tree. ## Output Print one number equal to . [samples]

给定一棵包含 $n$ 个顶点的树 $T$。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。定义函数 $I(x, y)$ 为连接顶点 $x$ 和 $y$ 的简单路径上所有 $a_i$ 的最大值与最小值之差。你的任务是计算。第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 树的顶点数。第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 10^6$) —— 写在顶点上的数字。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和顶点 $y$ 的边 ($1 ≤ x, y ≤ n$, $x ≠ y$)。保证这些边构成一棵树。请输出一个等于的数。 ## Input 第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 树的顶点数。第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 10^6$) —— 写在顶点上的数字。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和顶点 $y$ 的边 ($1 ≤ x, y ≤ n$, $x ≠ y$)。保证这些边构成一棵树。 ## Output 请输出一个等于的数。 [samples]

Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a_i \in \mathbb{Z} $ be the value assigned to vertex $ i \in V $. Define the function $ I(x, y) = \max_{v \in P_{x,y}} a_v - \min_{v \in P_{x,y}} a_v $, where $ P_{x,y} $ is the unique simple path between vertices $ x $ and $ y $ in $ T $. Compute: $$ \sum_{1 \leq x < y \leq n} I(x, y) $$

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "F. Imbalance Value of a Tree",
    "description": {
      "content": "You are given a tree _T_ consisting of _n_ vertices. A number is written on each vertex; the number written on vertex _i_ is _a__i_. Let's denote the function _I_(_x_, _y_) as the difference between m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF915F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree _T_ consisting of _n_ vertices. A number is written on each vertex; the number written on vertex _i_ is _a__i_. Let's denote the function _I_(_x_, _y_) as the difference between m...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一棵包含 $n$ 个顶点的树 $T$。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。定义函数 $I(x, y)$ 为连接顶点 $x$ 和 $y$ 的简单路径上所有 $a_i$ 的最大值与最小值之差。\n\n你的任务是计算 。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^6$) —— 树的顶点数。\n\n第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a_i \\in \\mathbb{Z} $ be the value assigned to vertex $ i \\in V $.\n\nDefine the function $ I(x, y) = \\max_{v \\in P_{x,y}} a_v - \\min_{v \\in P_{x,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments