WA on #21 求调

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141#include <bits/stdc++.h>
using namespace std;
#define intt long long
const int N = 1000005, M = 2000005;
int n,l,r,rt,u,cnt,head[N];
int ver[M],nxt[M],dep;
int siz[N],s[N];
bool tag[N];
intt ans;
struct seg
{
	intt c[N];
	void add(int x,int y)
	{
		while (x <= min(dep,r))
		{
			c[x] += y;
			x += (x & (-x));
		}
	}
	intt query(int x)
	{
		x = min(x,min(dep,r));
		intt res = 0;
		while (x)
		{
			res += c[x];
			x -= (x & (-x));
		}
		return res;
	}
	void clean()
	{
		for (int i=1;i<=dep;i++)
		{
			c[i] = 0;
		}
		return;
	}
}t,T;
void add(int x,int y)
{
	ver[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}
void dfs(int u)
{
	tag[u] = 1;
	s[u] = siz[u] = 1;
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		dfs(v);
		siz[u] += siz[v];
		s[u] = max(s[u],siz[v]);
	}
	tag[u] = 0;
}
void depth(int u,int len)
{
	tag[u] = 1;
	dep = max(dep,len);
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		depth(v,len+1);
	}
	tag[u] = 0;
}
void heavy(int u,int tot)
{
	tag[u] = 1;
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		heavy(v,tot);
	}
	s[u] = max(s[u],tot-siz[u]);
	if (s[u] < s[rt]) rt = u;
	tag[u] = 0;
}
void solve(int u,int len)
{
	tag[u] = 1;
	if (len > r) return;
	if (l <= len && len <= r) ans += len;
	if (l-len-1 >= 1) ans += (T.query(r-len) - T.query(l-len-1)) + (t.query(r-len) - t.query(l-len-1)) * len;
	else ans += T.query(r-len) + t.query(r-len) * len;
//	cout << u << ' ' << len << ' ' << ans << endl;
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		solve(v,len+1);
	}
	tag[u] = 0;
}
void update(int u,int len,int x)
{
	tag[u] = 1;
	if (len > r) return;
	t.add(len,x);
//	cout << "t.add: " << len << ' ' << x << endl; 
	T.add(len,x*len);
//	cout << "T.add: " << len << ' ' << x*len << endl; 
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		update(v,len+1,x);
	}
	tag[u] = 0;
}
void calc(int u)
{
	rt = u; dfs(u);
	heavy(u,siz[u]);
	dep = 0; depth(rt,0);
//	cout << rt << ' ' << dep << endl;
	t.clean(); 
	T.clean();
	tag[rt] = 1;
	for (int i=head[rt];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		solve(v,1);
		update(v,1,1);
	}
	for (int i=head[rt];i;i=nxt[i])
	{
		int v = ver[i];
		if (tag[v]) continue;
		calc(v);
	}
}
int main()
{
	scanf("%d%d%d",&n,&l,&r);
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&u);
		add(u,i); add(i,u);
	}
	calc(1);
	printf("%lld",ans);
	return 0;
}