#P7782. 「MCOI-Zero / AC6-M03」 Sipli Field

「MCOI-Zero / AC6-M03」 Sipli Field

题目背景

You've been ordered to start the mission now.

The interception op was a success, enemy air units around Khesed have been weakened, and the Republic of Emmeria's military has taken advantage of this prime opportunity to initiate a counterattack operation with all forces participating.

Enemy forces have established a wide-scale defensive line around Sipli Field, consisting largely of tank battalions.

Our ground forces are set up to cross the river and penetrate it, and eventually gain control of Khesed.

Garuda Team, we need you to support our advancing ground units, and eliminate all enemy forces. Multiple units will be simultaneously carrying out various operations on the ground.

Pay attention to the airspace above each operation area, and provide support as needed.

This must be the first time you've ever participated in a mission of this scale.

The battle simulator is a good way to get some practical experience under your belt.

Godspeed.

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 03} \\\Large\text{Sipli Field}\\\tiny -\textit{ Fortunes of War }-$$

题目描述

给定一个 nn 个点的树,和两个常数 L,RL,R

请对于每一个点 uu 求出有多少条路径过 uu 且长度 d[L,R]d\in [L,R]

输入格式

第一行三个整数 n,L,Rn,L,R

接下来 n1n-1 个整数,第 ii 个整数 fif_i 代表存在一条 fii+1f_i\leftrightarrow i+1 的双向边。

输出格式

nn 行,每行一个整数,表示对应点的答案。

5 1 3
1 1 2 2
7
9
4
4
4

提示

样例 1 解释:

  • 过 1 的路径:1-2, 1-3, 1-4, 1-5, 2-3, 4-3, 5-3
  • 过 2 的路径:2-1, 2-3, 2-4, 2-5, 1-4, 1-5, 3-4, 3-5, 4-5
  • 过 3 的路径:3-1, 3-2, 3-4, 3-5
  • 过 4 的路径:4-1, 4-2, 4-3, 4-5
  • 过 5 的路径:5-1, 5-2, 5-3, 5-4

  • Subtask 1(3 pts):R=1R=1
  • Subtask 2(7 pts):R2R\leq 2
  • Subtask 3(10 pts):n100n\leq 100
  • Subtask 4(10 pts):n2×103n\leq 2\times 10^3
  • Subtask 5(15 pts):n105,L=1,R=nn\leq 10^5,L=1,R=n
  • Subtask 6(15 pts):n105,L=Rn\leq 10^5,L=R
  • Subtask 7(20 pts):n105n\leq 10^5
  • Subtask 8(20 pts):无特殊限制。

对于 100%100\% 的数据,满足 1n1061\leq n\leq 10^61LRn1\leq L\leq R\leq n

idea:_Solowing_ClCN,solution:_Solowing_ClCN,code:_Solowing_ClCN,data:_Solowing_ClCN