#P16106. [2026年山东集训一轮]树邻域修改查询

[2026年山东集训一轮]树邻域修改查询

题目描述

这是一道函数式交互 / Grader 题。

选手程序需要包含头文件 data.h,并实现指定函数 solve。评测时,系统会将选手代码与评测主程序一起编译;评测主程序负责读取输入、调用 solve、输出答案并统计总代价。选手程序中不要自行编写 main 函数。

可以调用以下成员函数:

void Data::add_eq(const Data &a);
void Data::add(const Data &a, const Data &b);
void Data::clr();
bool Data::empty() const;

void Operation::apply(Data &w) const;
void Operation::apply(Operation &w) const;
void Operation::clr();
bool Operation::empty() const;

定义两种运算 ++ 与 ∗*。

对于任意 Data 类型元素 a,b,ca,b,c:

  • a.add_eq(b) 将 aa 修改为 a+ba+b;
  • a.add(b,c) 将 aa 修改为 b+cb+c;
  • a.clr() 将 aa 修改为 e+e_+,其中 e+e_+ 是 Data 类型关于 ++ 运算的单位元。

满足:

e++a=a+e+=a,e_+ + a = a + e_+ = a, a+b=b+a,a+b=b+a, (a+b)+c=a+(b+c).(a+b)+c=a+(b+c).

对于任意 Operation 类型元素 f,g,hf,g,h,以及任意 Data 类型元素 a,ba,b:

  • f.apply(a) 将 aa 修改为 f∗af*a;
  • f.apply(g) 将 gg 修改为 f∗gf*g;
  • f.clr() 将 ff 修改为 e∗e_*,其中 e∗e_* 是 Operation 类型关于 ∗* 运算的单位元。

满足:

(f∗g)∗h=f∗(g∗h),(f*g)*h=f*(g*h), (f∗g)∗a=f∗(g∗a),(f*g)*a=f*(g*a), f∗(a+b)=(f∗a)+(f∗b),f*(a+b)=(f*a)+(f*b), e∗∗f=f∗e∗=f,e_* * f = f * e_* = f, e∗∗a=a.e_* * a = a.

此外,Data 与 Operation 的构造函数、析构函数、赋值运算也是允许调用的。

你需要实现函数:

void solve(
    int n,
    int m,
    int fa[],
    Data d0[],
    int x[],
    int y[],
    Operation o[][2],
    Data ans[][2]);

给定一棵 nn 个结点的有根树,结点编号为 1,2,…,n1,2,\ldots,n。

对于 2≤i≤n2\le i\le n,fa[i] 表示结点 ii 的父亲,保证 fa[i] < i。

每个结点有一个状态信息,结点 ii 的初始状态为 d0[i]。

你需要依次执行 mm 次操作,操作编号为 0,1,…,m−10,1,\ldots,m-1。

第 ii 次操作由 x[i], y[i], o[i][0], o[i][1] 描述。你需要把结果保存到 ans[i][0] 和 ans[i][1] 中。

具体地,将树上所有结点分为两类:

  • 第一类:与结点 x[i] 的距离不超过 y[i] 的结点;
  • 第二类:不属于第一类的结点。

对于每个第一类结点 jj,按任意顺序等价地完成以下效果:

ans[i][0].add_eq(d0[j]);
o[i][0].apply(d0[j]);

对于每个第二类结点 jj,按任意顺序等价地完成以下效果:

ans[i][1].add_eq(d0[j]);
o[i][1].apply(d0[j]);

你可以使用其它等价操作来优化复杂度,但在 solve 结束后,必须保证 ans[i][0]、ans[i][1] 的值与上述朴素过程完全一致。

代价限制

计算 a+ba+b 或 a∗ba*b 时,若两个操作数都不是对应运算的单位元,则代价为 11;否则代价为 00。

总耗费为所有此类计算代价之和,必须不超过:

1.5×108.1.5\times 10^8.

若总代价超过限制,评测结果可能为运行错误或答案错误。

数据范围

对于 2020% 的数据,满足 n,m≤103n,m\le 10^3。

对于另外 2020% 的数据,满足 fa[i]=i−1fa[i]=i-1。

对于另外 2020% 的数据,满足 fa[i]=⌊i/2⌋fa[i]=\lfloor i/2\rfloor。

对于另外 2020% 的数据,满足 n,m≤3×104n,m\le 3\times 10^4。

对于所有数据:

1≤n,m≤105,1\le n,m\le 10^5, 1≤fa[i]≤i−1(2≤i≤n),1\le fa[i]\le i-1\quad (2\le i\le n), 1≤x[i]≤n(0≤i<m),1\le x[i]\le n\quad (0\le i<m), 0≤y[i]≤n−1(0≤i<m).0\le y[i]\le n-1\quad (0\le i<m).

提交说明

本题不是普通标准输入输出题。选手代码应只实现 solve 函数,不要写 main。

选手代码需要包含:

#include "data.h"

提交代码模板如下:

#include "data.h"

void solve(
    int n,
    int m,
    int fa[],
    Data d0[],
    int x[],
    int y[],
    Operation o[][2],
    Data ans[][2]
) {
    // 在这里实现你的算法。
}

请不要访问 Data 或 Operation 的私有成员,也不要假设它们的内部表示。程序只能通过题面给出的公开成员函数处理 Data 和 Operation 对象。

正式评测时,评测系统会自动提供 data.h 和评测主程序,选手只需要提交实现了 solve 的源代码。

本地测试说明

下发文件中提供了 local_test/ 目录,用于在本地测试公开样例。

Linux/macOS 环境下,可以进入 local_test 目录后运行:

chmod +x run_local.sh
./run_local.sh ../template.cpp 1

其中 ../template.cpp 是选手程序文件,最后的 1 表示测试第 11 组公开样例。

若要测试第 22 组样例,可以运行:

./run_local.sh ../template.cpp 2

脚本会生成 out_1.txt、out_2.txt 等输出文件,选手可以与 samples/1.ans、samples/2.ans 等答案文件进行比较。

如果无法运行脚本,也可以手动编译:

g++ -std=c++17 -O2 -pipe -I./include ../template.cpp local_grader.cpp -o local_run
./local_run < samples/1.in > out_1.txt

然后将 out_1.txt 与 samples/1.ans 比较。

注意:local_test/ 中的 local_grader.cpp、include/data.h 和 run_local.sh 仅供本地调试公开样例使用。正式提交时只需要提交实现了 solve 的源代码,评测系统会自动使用正式 grader。

@下发文件