P9992 [Ynoi Easy Round 2024] TEST_130 题解

· · 题解

最开始没看到子树的限制，以为是个极其困难题。

思路

由于问题是在子树下，可以考虑在 dfn 序上扫描线。

考虑一个点 u 对 v,d 的贡献。

令 dep_u 为 u 的深度，mdep_u 为 u 的子树下的最大深度。

这几个条件可以使用树状树组进行维护，那么我们做扫描线差分即可满足子树的限制。

Code

代码很好写，可能有一点卡常，加个快读就可以了。

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

#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)

typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;

bool ED;

const int N = 1000010;
const int mod = 998244353;

int n, m, tot, cnt, w[N], d[N], id[N];
int fa[N], dep[N], dfn[N], low[N], mdep[N], head[N];
i64 ans[N];
vector<int> add[N], del[N];
struct edge { int to, nxt; } e[N * 2];
struct Tree
{
    i64 t[N];
    inline int lb(int x) { return x & (-x); }
    inline void add(int x, int y) { while(x <= n) t[x] += y, x += lb(x); }
    inline i64 ask(int x) { i64 r = 0; while(x) r += t[x], x -= lb(x); return r; }
} t1, t2, t3;

const int I = 1e6; char buf[I], s[I], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+cin.rdbuf()->sgetn(buf,I),p1==p2)?EOF:*p1++)
template<typename T> inline void read(T &x)
{
    x = 0; int q = 1; char z;
    while(!isdigit(z = gc())) if(z == '-') q = -1;
    while(isdigit(z)) x = x * 10 + (z ^ 48), z = gc(); x *= q;
}
template<typename T> inline void put(T a)
{
    int tp = 0; if(!a) s[++tp] = 48;
    while(a) s[++tp] = a % 10 + 48 , a /= 10;
    while(tp) cout.rdbuf()->sputc(s[tp--]);
    cout.rdbuf()->sputc('\n');
}
inline void lnk(int x, int y)
{
    e[++cnt] = {y, head[x]}, head[x] = cnt;
    e[++cnt] = {x, head[y]}, head[y] = cnt;
}
inline void dfs(int now)
{
    id[dfn[now] = ++tot] = now;
    mdep[now] = dep[now] = dep[fa[now]] + 1;
    for(int i = head[now]; i; i = e[i].nxt)
        if(e[i].to != fa[now]) dfs(e[i].to), mdep[now] = max(mdep[now], mdep[e[i].to]);
    low[now] = tot;
}
inline void solve()
{
    read(n), read(m);
    fro(i, 2, n) read(fa[i]);
    fro(i, 2, n) lnk(i, fa[i]);
    dfs(1);
    fro(i, 1, m) read(w[i]), read(d[i]);
    fro(i, 1, m) del[dfn[w[i]]].eb(i);
    fro(i, 1, m) add[low[w[i]]].eb(i);
    fro(i, 1, n)
    {
        for(auto id : del[i])
        {
            i64 sum = t1.ask(min(n, dep[w[id]] + d[id]));
            sum -= t2.ask(min(n, dep[w[id]] + d[id]));
            sum += t3.ask(min(n, dep[w[id]] + d[id])) * (dep[w[id]] + d[id]);
            ans[id] -= sum;
        }
        int x = id[i];
        t1.add(mdep[x], mdep[x] - dep[x] + 1);
        t2.add(mdep[x], 1 - dep[x]);
        t3.add(mdep[x], -1);
        t2.add(dep[x], dep[x] - 1);
        t3.add(dep[x], 1);
        for(auto id : add[i])
        {
            i64 sum = t1.ask(min(n, dep[w[id]] + d[id]));
            sum -= t2.ask(min(n, dep[w[id]] + d[id]));
            sum += t3.ask(min(n, dep[w[id]] + d[id])) * (dep[w[id]] + d[id]);
            ans[id] += sum;
        }
    }
    fro(i, 1, m) put(ans[i]);
}

bool ST;

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    double Mib = fabs((&ED-&ST)/1048576.), Lim = 512;
    cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
    solve();
    return 0;
}