{"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一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n以下点对满足条件：$(1, 1)$，$(1, 3)$，$(1, 5)$，$(2, 2)$，$(3, 1)$，$(3, 3)$，$(3, 5)$，$(4, 4)$，$(5, 1)$，$(5, 3)$，$(5, 5)$。\n\n### 数据范围\n\n本题数据分为多个子任务，具体如下：\n\n| 子任务编号 | $n$ | 附加条件 | 子任务分数 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $\\leq 150$ | 无 | $10$ |\n| $2$ | $\\leq 1500$ | 无 | $10$ |\n| $3$ | $\\leq 10^5$ | 树为随机生成 | $10$ |\n| $4$ | $=99998$ | $a_i\\leq 300$ | $10$ |\n| $5$ | $=99998$ | $a$ 为 $1\\sim n$ 的排列 | $10$ |\n| $6$ | $\\leq 10^5$ | 无 | $50$ |\n\n对于所有数据，保证 $1 \\leq a_i \\leq n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4189","tags":["二分","2024","广东","最近公共祖先 LCA","排列组合","科创活动","小学活动"],"sample_group":[["5\n2 3 2 5 4\n1 2\n1 3\n2 4\n2 5","11"]],"created_at":"2026-03-03 11:09:25"}}