[中山市赛 2024] 树上开花

Luogu

IDLGB4189

Time1000ms

Memory512MB

DifficultyP4

二分2024广东最近公共祖先 LCA排列组合科创活动小学活动

你有一棵以 1 为根的树，统计点对 $(x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当 $x \neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。 ## Input 第一行一个整数 $n$。第二行 $n$ 个整数 $a_i$。第三到 $n + 1$ 行，每行两个整数，表示树上的边。 ## Output 一行一个整数表示答案。 [samples] ## Note ### 样例解释以下点对满足条件：$(1, 1)$，$(1, 3)$，$(1, 5)$，$(2, 2)$，$(3, 1)$，$(3, 3)$，$(3, 5)$，$(4, 4)$，$(5, 1)$，$(5, 3)$，$(5, 5)$。 ### 数据范围本题数据分为多个子任务，具体如下： | 子任务编号 | $n$ | 附加条件 | 子任务分数 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 150$ | 无 | $10$ | | $2$ | $\leq 1500$ | 无 | $10$ | | $3$ | $\leq 10^5$ | 树为随机生成 | $10$ | | $4$ | $=99998$ | $a_i\leq 300$ | $10$ | | $5$ | $=99998$ | $a$ 为 $1\sim n$ 的排列 | $10$ | | $6$ | $\leq 10^5$ | 无 | $50$ | 对于所有数据，保证 $1 \leq a_i \leq n$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[中山市赛 2024] 树上开花",
    "description": {
      "content": "你有一棵以 1 为根的树，统计点对 $(x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当 $x \\neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。 ",
      "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": "LGB4189"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一棵以 1 为根的树，统计点对 $(x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当\n$x \\neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数 $a_i$。\n\n第三到 $n + 1$ 行，每行两个整数，表示树上的边。\n\n## Output\n\n一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments