[蓝桥杯 2023 国 A] 相连的边

Luogu

IDLGP10418

Time1000ms

Memory512MB

DifficultyP4

2023树的遍历蓝桥杯国赛

给定一棵包含 $n$ 个结点的树，找出 $3$ 条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。 ## Input 输入第一行包含一个整数 $n$ 表示树的结点数。接下来 $n−1$ 行，每行包含两个整数，用一个空格分隔。其中第 $i$ 行的两个数 $x_i,y_i$，表示编号为 $i+1$ 和 $x_i$ 的结点之间有一条长度为 $y_i$ 的边。 ## Output 输出一行，包含一个整数表示满足要求的三条边的长度之和的最大值。 [samples] ## Note **【样例解释 1】** 结点 $2$ 和结点 $1$ 的边长为 $1$，结点 $3$ 和结点 $2$ 的边长为 $1$，结点 $4$ 和结点 $3$ 的边长为 $7$，结点 $5$ 和结点 $1$ 的边长为 $10$。 **【评测用例规模与约定】** 对于 $20\%$ 的评测用例，$4\le n\le 300$；对于 $40\%$ 的评测用例，$4\le n\le 5000$；对于所有评测用例，$4\le n\le 2\times 10^5$，$1\le x_i<i$，$1\le y_i\le 10^9$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2023 国 A] 相连的边",
    "description": {
      "content": "给定一棵包含 $n$ 个结点的树，找出 $3$ 条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10418"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵包含 $n$ 个结点的树，找出 $3$ 条边使得这三条边的端点仅经过这三条边即可互相到达且三条边的长度和尽可能大。\n\n## Input\n\n输入第一行包含一个整数 $n$ 表示树的结点数。\n\n接下来 $n−1$ 行，每行包含两个整数，用一个空格分隔。其中第 $i$ 行的两个数 $x_i,y_i$，表示编号为 $i+1$ 和 $x_i$ 的结点之间有一条长度为 $y_i$ 的边。\n\n## Ou...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments