{"problem":{"name":"[Ynoi2004] 2stmst","description":{"content":"已知 $n$ 个顶点的有根树，以及 $m$ 个二元组 $(x_i,y_i)$，其中 $x_i,y_i$ 是树的顶点。 对于树的顶点 $a,b$，定义 $D(a,b)$ 为：在以 $a$ 为根的子树中，但不在以 $b$ 为根的子树中的顶点个数。 你需要求出以这些二元组为顶点的完全图的最小生成树，其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8336"},"statements":[{"statement_type":"Markdown","content":"已知 $n$ 个顶点的有根树，以及 $m$ 个二元组 $(x_i,y_i)$，其中 $x_i,y_i$ 是树的顶点。\n\n对于树的顶点 $a,b$，定义 $D(a,b)$ 为：在以 $a$ 为根的子树中，但不在以 $b$ 为根的子树中的顶点个数。\n\n你需要求出以这些二元组为顶点的完全图的最小生成树，其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$。\n\n## Input\n\n第一行两个数表示 $n,m$。\n\n之后一行 $n-1$ 个数，其中第 $i$ 个数表示编号为 $i+1$ 的节点的父亲 $f_{i+1}$，保证 $f_{i+1}< i+1$。\n\n之后 $m$ 行，第 $i$ 行两个数 $x_i,y_i$，表示一个给定的二元组。\n\n## Output\n\n输出一个整数，表示最小生成树的边权和。\n\n[samples]\n\n## Note\n\nIdea：nzhtl1477，Solution：ccz181078( $O(m\\log n\\log m+n\\log n)$ )，Rainbow_qwq( $O(m\\log n+n)$ )，Code：ccz181078&djq_cpp&Rainbow_qwq，Data：ccz181078\n\n样例解释：\n\n最小生成树包含边 $(1,4,1),(2,3,3),(2,4,3)$，三元组表示第一个二元组的编号，第二个二元组的编号，边权。边权和为 $7$。\n\n数据范围：\n\n对于 $100\\%$ 的数据，满足 $1\\le n\\le 10^6,1\\le m\\le 10^5$。对任意 $i=1,2,\\dots n-1$，满足 $1\\le f_{i+1}<i+1$。对任意 $i=1,2,\\dots m$，满足 $1\\le x_i,y_i\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8336","tags":["2004","O2优化","Ynoi"],"sample_group":[["5 4\n1 2 3 3\n3 5\n2 2\n5 2\n2 5\n","7\n"]],"created_at":"2026-03-03 11:09:25"}}