J. Send the Fool Further! (easy)

Codeforces

IDCF802J

Time1000ms

Memory256MB

Difficulty—

dfs and similargraphstrees

English · Original

Chinese · Translation

Formal · Original

Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on. Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank? Heidi's _n_ friends are labeled 0 through _n_ - 1, and their network of connections forms a tree. In other words, every two of her friends _a_, _b_ know each other, possibly indirectly (there is a sequence of friends starting from _a_ and ending on _b_ and such that each two consecutive friends in the sequence know each other directly), and there are exactly _n_ - 1 pairs of friends who know each other directly. Jenny is given the number 0. ## Input The first line of the input contains the number of friends _n_ (3 ≤ _n_ ≤ 100). The next _n_ - 1 lines each contain three space-separated integers _u_, _v_ and _c_ (0 ≤ _u_, _v_ ≤ _n_ - 1, 1 ≤ _c_ ≤ 104), meaning that _u_ and _v_ are friends (know each other directly) and the cost for travelling between _u_ and _v_ is _c_. It is guaranteed that the social network of the input forms a tree. ## Output Output a single integer – the maximum sum of costs. [samples] ## Note In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).

Heidi 的朋友 Jenny 请 Heidi 将一封重要信件送达他们共同的某位朋友。由于 Jenny 是爱尔兰人，Heidi 认为这可能是个恶作剧。更准确地说，她怀疑这封信的内容是："Send the fool further!"（把傻子送得更远！），而当收件人读到这封信后，会要求 Heidi 将同样的消息再转交给另一位与 Heidi 有共同联系的朋友，如此继续下去。 Heidi 相信她的朋友们希望避免尴尬的局面，因此她不会被要求访问同一个人（包括 Jenny）两次。她还知道她任意两位互相认识的朋友之间旅行所需的费用。她想知道：如果这真的是一场恶作剧，她最多会浪费多少钱在旅途中？ Heidi 的 #cf_span[n] 位朋友编号为 #cf_span[0] 到 #cf_span[n - 1]，他们之间的连接网络构成一棵树。换句话说，任意两位朋友 #cf_span[a]、#cf_span[b] 都通过若干间接或直接的联系相互认识（存在一个从 #cf_span[a] 开始、以 #cf_span[b] 结束的朋友序列，使得序列中每两个相邻的朋友都直接认识），且恰好有 #cf_span[n - 1] 对朋友是直接认识的。 Jenny 的编号为 #cf_span[0]。输入的第一行包含朋友的数量 #cf_span[n]（#cf_span[3 ≤ n ≤ 100]）。接下来的 #cf_span[n - 1] 行，每行包含三个用空格分隔的整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[0 ≤ u, v ≤ n - 1]，#cf_span[1 ≤ c ≤ 104]），表示 #cf_span[u] 和 #cf_span[v] 是朋友（直接认识），且在他们之间旅行的费用为 #cf_span[c]。保证输入的社会网络构成一棵树。请输出一个整数——最大的总花费。在第二个例子中，最坏情况如下：Jenny 让 Heidi 去编号为 #cf_span[2] 的朋友那里（花费 #cf_span[100]），然后朋友 #cf_span[2] 让她去朋友 #cf_span[1]（花费 #cf_span[3]），最后朋友 #cf_span[1] 让她去朋友 #cf_span[4]（额外花费 #cf_span[2]）。 ## Input 输入的第一行包含朋友的数量 #cf_span[n]（#cf_span[3 ≤ n ≤ 100]）。接下来的 #cf_span[n - 1] 行，每行包含三个用空格分隔的整数 #cf_span[u]、#cf_span[v] 和 #cf_span[c]（#cf_span[0 ≤ u, v ≤ n - 1]，#cf_span[1 ≤ c ≤ 104]），表示 #cf_span[u] 和 #cf_span[v] 是朋友（直接认识），且在他们之间旅行的费用为 #cf_span[c]。保证输入的社会网络构成一棵树。 ## Output 请输出一个整数——最大的总花费。 [samples] ## Note 在第二个例子中，最坏情况如下：Jenny 让 Heidi 去编号为 #cf_span[2] 的朋友那里（花费 #cf_span[100]），然后朋友 #cf_span[2] 让她去朋友 #cf_span[1]（花费 #cf_span[3]），最后朋友 #cf_span[1] 让她去朋友 #cf_span[4]（额外花费 #cf_span[2]）。

Given a tree $ T = (V, E) $ with $ n $ vertices labeled $ 0 $ through $ n-1 $, where vertex $ 0 $ corresponds to Jenny, and each edge $ (u, v) \in E $ has a positive integer weight $ c $ representing the travel cost. Find the maximum total cost of a simple path (i.e., a path with no repeated vertices) starting at vertex $ 0 $. This is equivalent to finding the longest path (in terms of edge weight sum) starting from vertex $ 0 $ in a tree. Formally: - Let $ T $ be a tree with vertex set $ V = \{0, 1, \dots, n-1\} $ and edge set $ E $, where each edge $ e = (u, v) \in E $ has weight $ w(e) = c \in \mathbb{Z}^+ $. - Let $ P $ be a simple path starting at vertex $ 0 $: $ P = (v_0 = 0, v_1, v_2, \dots, v_k) $, where $ k \geq 1 $, and $ (v_i, v_{i+1}) \in E $ for all $ i $, with all $ v_i $ distinct. - Define the cost of $ P $ as $ \sum_{i=0}^{k-1} w(v_i, v_{i+1}) $. - Objective: $ \max_{P \text{ is a simple path starting at } 0} \text{cost}(P) $. This is the **maximum path sum from vertex 0 to any leaf** in the tree.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "J. Send the Fool Further! (easy)",
    "description": {
      "content": "Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Heidi 的朋友 Jenny 请 Heidi 将一封重要信件送达他们共同的某位朋友。由于 Jenny 是爱尔兰人，Heidi 认为这可能是个恶作剧。更准确地说，她怀疑这封信的内容是：\"Send the fool further!\"（把傻子送得更远！），而当收件人读到这封信后，会要求 Heidi 将同样的消息再转交给另一位与 Heidi 有共同联系的朋友，如此继续下去。\n\nHeidi 相信她的朋友...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a tree $ T = (V, E) $ with $ n $ vertices labeled $ 0 $ through $ n-1 $, where vertex $ 0 $ corresponds to Jenny, and each edge $ (u, v) \\in E $ has a positive integer weight $ c $ representing ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments