[蓝桥杯 2023 国 A] 树上的路径

Luogu
IDLGP10421
Time6000ms
Memory1024MB
DifficultyP5
线段树点分治树状数组2023分治容斥原理蓝桥杯国赛
给定一棵包含 $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$ 和结点 $j$ 之间的距离,$[C]$ 表示条件 $C$ 满足时取 $1$,不满足时取 $0$。 ## Input 输入的第一行包含三个整数 $n, L, R$,相邻两个整数之间使用一个空格分隔。 接下来 $n−1$ 行,每行包含一个整数,其中第 $i$ 行的整数 $F_i$ 表示第 $i+1$ 个结点在树上的父亲结点。结点 $1$ 是根结点,没有父亲结点。 ## Output 输出一行包含一个整数表示答案。 [samples] ## Note **【评测用例规模与约定】** 对于 $40\%$ 的评测用例,$n\le 2000$; 对于所有评测用例,$1\le L\le R\le n\le 10^6$,$1\le F_i\le i$。
Samples
Input #1
4 2 3
1
1
3
Output #1
7
API Response (JSON)
{
  "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$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments