{"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 maximum and minimum value of _a__i_ on a simple path connecting vertices _x_ and _y_.\n\nYour task is to calculate .\n\n## Input\n\nThe first line contains one integer number _n_ (1 ≤ _n_ ≤ 106) — the number of vertices in the tree.\n\nThe second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the numbers written on the vertices.\n\nThen _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.\n\n## Output\n\nPrint one number equal to .\n\n[samples]","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_n$ ($1 ≤ a_i ≤ 10^6$) —— 写在顶点上的数字。\n\n接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接顶点 $x$ 和顶点 $y$ 的边 ($1 ≤ x, y ≤ n$, $x ≠ y$)。保证这些边构成一棵树。\n\n请输出一个等于 的数。\n\n## Input\n\n第一行包含一个整数 $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$)。保证这些边构成一棵树。\n\n## Output\n\n请输出一个等于 的数。\n\n[samples]","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,y}} a_v $, where $ P_{x,y} $ is the unique simple path between vertices $ x $ and $ y $ in $ T $.\n\nCompute:\n$$\n\\sum_{1 \\leq x < y \\leq n} I(x, y)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF915F","tags":["data structures","dsu","graphs","trees"],"sample_group":[["4\n2 2 3 1\n1 2\n1 3\n1 4","6"]],"created_at":"2026-03-03 11:00:39"}}