F. Minimize Tree

Codeforces

IDCF10105F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes. The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w. *Constraints:* 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N, - 103 ≤ w ≤ 103 Output a single integer, the minimum sum of distances from node 1 to all other nodes. ## Input The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.*Constraints:* 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N, - 103 ≤ w ≤ 103 ## Output Output a single integer, the minimum sum of distances from node 1 to all other nodes. [samples]

**Definitions** Let $ T = (V, E) $ be a weighted undirected tree with $ |V| = N $, rooted at node $ 1 $. Let $ w(e) \in \mathbb{Z} $ denote the weight of edge $ e \in E $, with $ |E| = N - 1 $. Let $ d_T(u, v) $ denote the shortest path distance between nodes $ u $ and $ v $ in $ T $. Let $ D_T = \sum_{v \in V \setminus \{1\}} d_T(1, v) $ be the total distance from root $ 1 $ to all other nodes in $ T $. **Constraints** 1. $ 1 \leq N \leq 5 \times 10^4 $ 2. For each edge $ (u, v, w) \in E $: $ 1 \leq u, v \leq N $, $ -10^3 \leq w \leq 10^3 $ 3. Exactly one edge $ e \in E $ may be removed, and one edge $ e' \notin E $ of weight $ w(e) $ may be added, such that the resulting graph is still a tree. **Objective** Minimize $ D_{T'} = \sum_{v \in V \setminus \{1\}} d_{T'}(1, v) $ over all valid transformations $ T' $ of $ T $, where $ T' $ is obtained by replacing one edge $ e \in E $ with another edge $ e' $ of the same weight such that $ T' $ remains a tree.

API Response (JSON)

{
  "problem": {
    "name": "F. Minimize Tree",
    "description": {
      "content": "Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10105F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a weighted undirected tree with $ |V| = N $, rooted at node $ 1 $.  \nLet $ w(e) \\in \\mathbb{Z} $ denote the weight of edge $ e \\in E $, with $ |E| = N - 1 $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments