题目描述

这是一道函数式交互 / 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,c$：

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

满足：

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

对于任意 Operation 类型元素 $f,g,h$，以及任意 Data 类型元素 $a,b$：

• f.apply(a) 将 $a$ 修改为 $f*a$；
• f.apply(g) 将 $g$ 修改为 $f*g$；
• f.clr() 将 $f$ 修改为 $e_*$，其中 $e_*$ 是 Operation 类型关于 $*$ 运算的单位元。

满足：

$$(f*g)*h=f*(g*h),$$ $$(f*g)*a=f*(g*a),$$ $$f*(a+b)=(f*a)+(f*b),$$ $$e_* * f = f * e_* = f,$$ $$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]);

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

对于 $2\le i\le n$，fa[i] 表示结点 $i$ 的父亲，保证 fa[i] < i。

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

你需要依次执行 $m$ 次操作，操作编号为 $0,1,\ldots,m-1$。

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

具体地，将树上所有结点分为两类：

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

对于每个第一类结点 $j$，按任意顺序等价地完成以下效果：

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

对于每个第二类结点 $j$，按任意顺序等价地完成以下效果：

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

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

代价限制

计算 $a+b$ 或 $a*b$ 时，若两个操作数都不是对应运算的单位元，则代价为 $1$；否则代价为 $0$。

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

$$1.5\times 10^8.$$

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

数据范围

对于 $20$ 的数据，满足 $n,m\le 10^3$。

对于另外 $20$ 的数据，满足 $fa[i]=i-1$。

对于另外 $20$ 的数据，满足 $fa[i]=\lfloor i/2\rfloor$。

对于另外 $20$ 的数据，满足 $n,m\le 3\times 10^4$。

对于所有数据：

$$1\le n,m\le 10^5,$$ $$1\le fa[i]\le i-1\quad (2\le i\le n),$$ $$1\le x[i]\le n\quad (0\le 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 表示测试第 $1$ 组公开样例。

若要测试第 $2$ 组样例，可以运行：

./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。

@下发文件