• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 【题解】Ynoi 2008 rdCcot

3小时前 3次浏览

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define fi first
#define se second
#define rez resize
#define pb push_back
#define mkp make_pair

#define Lep(i, l, r) for (int i = l; i < r; ++ i)
#define Rep(i, r, l) for (int i = r; i > l; -- i)
#define lep(i, l, r) for (int i = l; i <= r; ++ i)
#define rep(i, r, l) for (int i = r; i >= l; -- i)

namespace io {
const int SIZE = (1 << 25) + 1;
char ibuf[SIZE], *iS, *iT;
char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[16];
int f, qr;

#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)

inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
template <class I> inline void IN (I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
x = f == -1 ? -x : x;
}
template <class I> inline void print (I x) {
if (! x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[ ++ qr] = x % 10 + '0',  x /= 10;
while (qr) putc (qu[qr -- ]);
}
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: IN;
using io :: putc;
using io :: print;

template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }

const int N = 3e5 + 5;

int n, m, C, L[N], R[N], rk[N], id[N];

struct edge { int nxt, to; } G[N << 1];
inline void addedge (int u, int v) {
}

struct fhq_treap {// {{{ fhq treap
int rt, cnt;
struct node { int lc, rc, mi, id, siz, rnd, val; } t[N];

inline int newnode (int id, int val) {
++ cnt, t[cnt].mi = t[cnt].val = val, t[cnt].siz = 1, t[cnt].rnd = rand (), t[cnt].id = id;
return cnt;
}
inline void pushup (int x) {
t[x].mi = min (t[x].val, min (t[t[x].lc].mi, t[t[x].rc].mi));
t[x].siz = t[t[x].lc].siz + t[t[x].rc].siz + 1;
}
inline void clear () {
rt = 0; while (cnt) t[cnt].lc = t[cnt].rc = 0, -- cnt;
}

void split (int now, int k, int &x, int &y) {
if (! now) return x = y = 0, void ();
if (t[now].id <= k) x = now, split (t[x].rc, k, t[x].rc, y), pushup (x);
else y = now, split (t[y].lc, k, x, t[y].lc), pushup (y);
}
int merge (int x, int y) {
if (! x || ! y) return x | y;
if (t[x].rnd <= t[y].rnd) return t[x].rc = merge (t[x].rc, y), pushup (x), x;
else return t[y].lc = merge (x, t[y].lc), pushup (y), y;
}

inline void calc (const int &id, const int &val) {
int lim = C - val, _tx, _ty, _tz;
split (rt, id, _tx, _ty);

_tz = _tx; while (_tz && t[_tz].mi <= lim) {
if (t[_tz].val <= lim) chkmax (L[id], t[_tz].id), _tz = t[_tz].rc;
else _tz = (t[_tz].rc && t[t[_tz].rc].mi <= lim) ? t[_tz].rc : t[_tz].lc;
}
_tz = _ty; while (_tz && t[_tz].mi <= lim) {
if (t[_tz].val <= lim) chkmin (R[id], t[_tz].id), _tz = t[_tz].lc;
else _tz = (t[_tz].lc && t[t[_tz].lc].mi <= lim) ? t[_tz].lc : t[_tz].rc;
}
rt = merge (merge (_tx, newnode (id, val)), _ty);
}
} t; // }}}

// {{{ tree divide

bool vis[N];
int rt, all, len, mxp[N], dep[N], siz[N], pot[N];

void init (int u, int pre) {
dep[u] = dep[pre] + 1;
for (int v, i = head[u]; i; i = G[i].nxt) if (v = G[i].to, v != pre) init (v, u);
}
void getsiz (int u, int pre) {
siz[u] = 1;
for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getsiz (v, u), siz[u] += siz[v];
}
void getrt (int u, int pre) {
mxp[u] = all - siz[u];
for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getrt (v, u), chkmax (mxp[u], siz[v]);
if (mxp[u] < mxp[0]) rt = u, mxp[0] = mxp[u];
}

void getpot (int u, int pre) {
pot[ ++ len] = u, dep[u] = dep[pre] + 1;
for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getpot (v, u);
}

void divide (int u) {
vis[u] = true, pot[len = 1] = u, dep[u] = 0;
for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to]) getpot (v, u);
sort (pot + 1, pot + 1 + len, [&](const int x, const int y) { return rk[x] < rk[y]; });

lep (i, 1, len) t.calc (pot[i], dep[pot[i]]);
t.clear ();

for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to])
getsiz (v, u), all = siz[v], mxp[0] = all + 1, getrt (v, u), divide (rt);
}

// }}}

int tu, tc[N], ans[N << 1];

inline int lowbit (int x) { return x & (-x); }
inline void modify (int x, int y) { while (x <= n) tc[x] += y, x += lowbit (x); }
inline int query (int x) { int res = 0; while (x) res += tc[x], x -= lowbit (x); return res; }

int main () {
srand (time (0));

IN (n), IN (m), IN (C);
lep (i, 2, n) IN (tu), addedge (i, tu);

lep (i, 1, n) L[i] = 0, R[i] = n + 1, id[i] = i;
init (1, 0), sort (id + 1, id + 1 + n, [&](const int x, const int y) {
return dep[x] == dep[y] ? x < y : dep[x] < dep[y];
});
lep (i, 1, n) rk[id[i]] = i;

t.t[0].mi = t.t[0].val = n + 1;
lep (i, 1, n) dep[i] = 0;
getsiz (1, 0), all = siz[1], mxp[0] = all + 1, getrt (1, 0), divide (rt);
lep (i, 1, n) ++ L[i], -- R[i];

for (int i = 1, l, r; i <= m; ++ i) IN (l), IN (r), qsta[r].pb (mkp (l, i));
lep (i, 1, n) add[i].pb (mkp (L[i], i)), del[R[i] + 1].pb (mkp (L[i], i));

lep (i, 1, n) {
for (auto now : add[i]) modify (now.fi, 1), modify (now.se + 1, -1);
for (auto now : del[i]) modify (now.fi, -1), modify (now.se + 1, 1);
for (auto now : qsta[i]) ans[now.se] = query (now.fi);
}
lep (i, 1, m) print (ans[i]), putc ('n');
return 0;
}
``````