{"problem":{"name":"[蓝桥杯 2023 国 A] 树上的路径","description":{"content":"给定一棵包含 $n$ 个结点的树，树的每条边的长度均为 $1$。求这棵树的所有长度在 $L\\sim R$ 之间的路径的长度之和。两条路径经过的边集完全相同时视作同一条路径。 也就是求 $\\sum\\limits_{i=1}^n{\\sum\\limits_{j=i+1}^{n}{dis(i,j)\\cdot[L \\le dis(i,j) \\le R]}}$，其中 $dis(i,j)$ 表示结点 $i$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10421"},"statements":[{"statement_type":"Markdown","content":"给定一棵包含 $n$ 个结点的树，树的每条边的长度均为 $1$。求这棵树的所有长度在 $L\\sim R$ 之间的路径的长度之和。两条路径经过的边集完全相同时视作同一条路径。\n\n也就是求 $\\sum\\limits_{i=1}^n{\\sum\\limits_{j=i+1}^{n}{dis(i,j)\\cdot[L \\le dis(i,j) \\le R]}}$，其中 $dis(i,j)$ 表示结点 $i$ 和结点 $j$ 之间的距离，$[C]$ 表示条件 $C$ 满足时取 $1$，不满足时取 $0$。\n\n## Input\n\n输入的第一行包含三个整数 $n, L, R$，相邻两个整数之间使用一个空格分隔。\n\n接下来 $n−1$ 行，每行包含一个整数，其中第 $i$ 行的整数 $F_i$ 表示第 $i+1$ 个结点在树上的父亲结点。结点 $1$ 是根结点，没有父亲结点。\n\n## Output\n\n输出一行包含一个整数表示答案。\n\n[samples]\n\n## Note\n\n**【评测用例规模与约定】**\n\n对于 $40\\%$ 的评测用例，$n\\le 2000$；  \n对于所有评测用例，$1\\le L\\le R\\le n\\le 10^6$，$1\\le F_i\\le i$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10421","tags":["线段树","点分治","树状数组","2023","分治","容斥原理","蓝桥杯国赛"],"sample_group":[["4 2 3\n1\n1\n3\n","7"]],"created_at":"2026-03-03 11:09:25"}}