# 通知村民 · 题解

## 1. 思路

把最终的通知方式看成一棵（一批）树：每个人要么由 33DAI **亲自通知**（花 $p$），
要么由某个已经知道通知的村民 $u$ **转告**（花 $b_u$）——于是每个人都恰好有一个"上级"，
顺着上级走一定停在某个被亲自通知的人身上（不会绕圈）。
每个村民 $u$ 最多有 $a_u$ 个"下级"。

设最后有 $k$ 个人是被亲自通知的，另外 $m = n - k$ 个人是被转告的，那么

$$\text{总花费} = k\cdot p + \sum_{\text{被转告的每个人 } x} b_{\text{上级}(x)}.$$

也就是说：**每一次转告都是"买一个名额"，买谁的名额就付谁的 $b$**，
每个村民最多卖出 $a_i$ 个名额；卖名额的人自己也必须被通知到。

1. 至少要有一个名额来自"亲自通知"的人，所以 $k \ge 1$，即答案里至少有一个 $p$；
2. 想让 $\sum b$ 尽量小，显然要**先买最便宜的名额**：把村民按 $b$ 升序排，
   依次用掉他们的 $a_i$ 个名额；
3. 若某个名额的价格已经不比自己通知便宜（$b_i \ge p$），那就不该买它——
   剩下的 $m$ 个人还不如 33DAI 亲自通知（每人 $p$）。

于是：先花一次 $p$ 亲自通知一个人（哪个都行，取 $b$ 最小的那个最自然），
然后按 $b$ 从小到大遍历，只要 $b_i < p$ 就买下 $\min(a_i, \text{剩余人数})$ 个名额，
遇到第一个 $b_i \ge p$ 就停下，剩下的村民全部由 33DAI 亲自通知。

**和"没买名额"的方案比**：如果所有 $b_i$ 都 $\ge p$，答案就是 $n\cdot p$；
否则上面的做法会把名额一直买到"不划算"为止，恰好是两种方案的最优折中。

## 2. 复杂度

每个测试用例排序 $O(n\log n)$，之后线性扫一遍；总复杂度 $O(\sum n\log n)$，空间 $O(n)$。

## 3. 实现要点

- **答案需要 64 位**：$n \le 10^5$ 且 $p \le 10^5$，$n\cdot p$ 最大 $10^{10}$，
  超出 `int`，所以累加用 `long long`（中间量 `use * b` 也要用 `long long`）。
- **别忘了最开始那一次 $p$**：别人能转告的前提是"已经有人知道了"，
  所以循环开始前答案先加上一个 $p$、剩余人数从 $n-1$ 开始。
- **边界**：$n = 1$ 时答案是 $p$；$p = 1$ 时所有 $b_i \ge 1 = p$，一名名额都不买，答案是 $n$。
- **两行数组的读入**：$a$ 和 $b$ 都在各自的一整行里，先读完 $n$ 个 $a_i$，再读 $n$ 个 $b_i$。
- 只有一次 `sort`，多组数据共用一个 `vector` 即可。

## 4. 参考程序（与 `src/std.cpp` 一致）

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;

struct Person
{
    long long a, b; // a：这个人最多能转告多少名村民；b：他每转告一人的花费
};

bool cmpPerson(const Person &x, const Person &y)
{
    return x.b < y.b;
}

int main()
{
    // 文件 IO：文件名与题面、config.yaml 的 filename 一致
    freopen("spread.in", "r", stdin);
    freopen("spread.out", "wb", stdout);
    int t;
    scanf("%d", &t);
    vector<Person> per(MAXN + 5); // per[0..n-1]：按 b 从小到大排好的村民
    while (t--)
    {
        int n;
        long long p;
        scanf("%d%lld", &n, &p);
        for (int i = 0; i < n; i++)
            scanf("%lld", &per[i].a);
        for (int i = 0; i < n; i++)
            scanf("%lld", &per[i].b);
        sort(per.begin(), per.begin() + n, cmpPerson);
        // 至少要有一个人是被 33DAI 亲自通知的（所以先付一次 p）
        long long ans = p;
        long long left = n - 1; // 除第一个之外还没被通知到的村民数
        for (int i = 0; i < n && left > 0; i++)
        {
            if (per[i].b >= p)
                break;
            long long use = min(per[i].a, left);
            ans += use * per[i].b;
            left -= use;
        }
        ans += left * p; // 剩下的人由 33DAI 亲自通知，每人 p
        printf("%lld\n", ans);
    }
    return 0;
}
```

## 5. 子任务说明

| 子任务 | 测试点 | 限制 | 想放过的写法 |
| :---: | :---: | :--- | :--- |
| 1 | 1 ~ 6 | $n \le 1000$ | 朴素做法：每次线性找当前最便宜的可买名额，$O(n^2)$ 也能过 |
| 2 | 7 ~ 12 | 所有 $b_i \le p$ | 不必判断"买名额 vs 亲自通知"，直接一路买最便宜的名额即可 |
| 3 | 13 ~ 20 | 无额外限制，$\sum n$ 卡满 $10^5$ | 正解；还要处理 $b_i > p$、$p = 1$、$a_i = 1$ 与 64 位答案 |

# 前缀和之谜 · 题解

## 1. 思路

给出的 $k$ 个数是 $s_{n-k+1}, \dots, s_n$，它们把序列 $a$ 的**尾部**完全确定了下来：

$$a_i = s_i - s_{i-1} \quad (n-k+2 \le i \le n).$$

于是有两个必要条件：

1. **尾部必须不降**：$a_{n-k+2} \le a_{n-k+3} \le \dots \le a_n$，
   也就是这些相邻差 $s_i - s_{i-1}$ 必须单调不降；
2. **首段必须装得下**：剩下的 $n-k+1$ 个元素（$a_1, \dots, a_{n-k+1}$）之和恰好是
   $s_{n-k+1}$，而它们每一个都不能超过 $a_{n-k+2} = s_{n-k+2} - s_{n-k+1}$。
   由于整数序列里首段元素可以取任意小，所以只要
   $s_{n-k+1} \le (n-k+1)\cdot a_{n-k+2}$ 就一定能构造出来。

两条都满足时，直接令

$$a_1 = s_{n-k+1} - (n-k)\cdot d,\qquad a_2 = a_3 = \dots = a_{n-k+1} = d$$

（其中 $d = s_{n-k+2} - s_{n-k+1}$）即可，序列不降且后缀前缀和与输入一致。

$k = 1$ 时没有任何差分被确定，取 $a_1 = s_n$、其余元素随便取（例如都取 $a_1$）就行，答案恒为 `Yes`。

## 2. 复杂度

每个测试用例 $O(k)$，所有测试用例合计 $O(\sum n)$；空间 $O(k)$。

## 3. 实现要点

- 容量判定里 $(n-k+1)\cdot a_{n-k+2}$ 最大约 $10^5 \times 2\times 10^9 = 2\times 10^{14}$，
  必须用 `long long`；差分本身也能到 $2\times 10^9$，同样不能落到 `int`。
- `k = 1` 要单独处理，否则会去读第二个前缀和。
- 多组数据共用一个 `s` 数组即可，读入时只读 $k$ 个。

## 4. 参考程序（与 `src/std.cpp` 一致）

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;

int main()
{
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "wb", stdout);
    int t;
    scanf("%d", &t);
    vector<long long> s(MAXN + 5); // s[0..k-1]：本题给出的最后 k 项前缀和
    while (t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < k; i++)
            scanf("%lld", &s[i]);
        bool ok = true;
        if (k >= 2)
        {
            long long len = n - k + 1;     // 前缀和没有给出的那一段长度（首段）
            long long first = s[1] - s[0]; // 首段每个元素的上界
            if (s[0] > len * first)        // 首段全取上界也凑不出 s[0]，则不可能
                ok = false;
            for (int i = 2; i < k; i++) // 已知部分被差分唯一确定，差分必须不降
                if (s[i] - s[i - 1] < s[i - 1] - s[i - 2])
                    ok = false;
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
}
```

## 5. 子任务说明

| 子任务 | 测试点 | 限制 | 想放过的写法 |
| :---: | :---: | :--- | :--- |
| 1 | 1 ~ 6 | $n \le 8$，数值也很小 | 枚举 / 手动构造首段 |
| 2 | 7 ~ 12 | $k = n$ | 只需检查差分不降（首段长度恒为 1） |
| 3 | 13 ~ 20 | 无额外限制，$\sum n$ 卡满 $10^5$ | 正解；两条必要条件一条都不能少，且必须用 64 位 |

# 城市天际线 题解

## 思路

### 1. 每个位置加盖多少层是独立的

设 $c_i$ 表示"只把第 $i$ 栋楼房顶成波峰"所需加盖的层数：

$$c_i = \max\bigl(0,\ \max(h_{i-1}, h_{i+1}) + 1 - h_i\bigr),\qquad i = 2, 3, \dots, n-1$$

$c_1 = c_n = 0$（街道两端的楼房不可能比街道外面更高）。

关键观察：**要顶成波峰，只需要第 $i$ 栋比"原来"的左右两栋高**，不必关心左右两栋有没有被加盖过
（题面只说加盖不能拆楼，别的位置盖多高都不影响"第 $i$ 栋比它们高"这件事）。
所以选定一组位置 $S$ 之后，总加盖层数恰好就是 $\sum_{i \in S} c_i$，各位置之间互不影响。

### 2. 最多能把几栋变成酷的

酷的楼房必须比左右两栋都高，所以两个酷的楼房不能相邻；又只有第 $2 \sim n-1$ 栋可能变酷。
从位置 $\{2, 3, \dots, n-1\}$ 里挑两两不相邻的位置，最多能挑

$$k = \left\lceil \frac{n-2}{2} \right\rceil$$

个。这个上界是能达到的：

- $n$ 为奇数：位置 $2, 4, \dots, n-1$ 一共恰好 $k = \dfrac{n-1}{2}$ 个，两两不相邻；
- $n$ 为偶数：位置 $2, 4, \dots, n-2$ 一共恰好 $k = \dfrac{n}{2}-1$ 个，两两不相邻。

于是问题变成：从 $\{2, \dots, n-1\}$ 里挑 $k$ 个两两不相邻的位置，让 $\sum c_i$ 最小。

### 3. 大小为 $k$ 的最优位置集合长什么样

- **$n$ 为奇数**：位置 $2, 4, \dots, n-1$ 恰好 $k$ 个且两两不相邻，已经取满 $k$ 个；
  任何别的大小为 $k$ 的集合都会多占一个奇数位置，必然和相邻的偶数位置冲突。
  所以方案**唯一**，答案就是这些位置的 $c_i$ 之和。

- **$n$ 为偶数**：记
  - 偶位置 $E = \{2, 4, \dots, n-2\}$（$k$ 个），
  - 奇位置 $O = \{3, 5, \dots, n-1\}$（$k$ 个）。

  大小为 $k$ 的合法集合一定形如"$E$ 里前 $j$ 个"并上"$O$ 里后 $k-j$ 个"（$j = 0, 1, \dots, k$）。
  于是枚举 $j$，用前后缀和 $O(1)$ 算出总代价，取最小值即可。

  > 为什么正好是这种形状：$E$ 里相邻两个相差 $2$，$O$ 里相邻两个也相差 $2$，
  > 所以"取 $E$ 的前 $j$ 个"与"取 $O$ 的后 $k-j$ 个"拼起来恰好 $k$ 个、且两两不相邻。
  > 反过来，任何 $k$ 个两两不相邻的位置，把它们按奇偶分类后一定呈这种"左边偏偶、右边偏奇"的形态
  >（若某个偶位置被跳过、它右边又有奇位置被跳过，个数就凑不满 $k$）。

## 算法与复杂度

对每组数据：

1. 预处理 $c_2 \sim c_{n-1}$；
2. 预处理两个前后缀和：
   - `pre[i]`：偶数位置 $\le i$ 的 $c$ 之和；
   - `suf[i]`：奇数位置 $\ge i$ 的 $c$ 之和。
3. $n$ 为奇数 → 答案 $= pre[n-1]$；
   $n$ 为偶数 → 答案 $=\min\limits_{j=0}^{k}\bigl(pre[2j] + suf[2j+3]\bigr)$。

时间复杂度 $O(n)$（每个测试点），空间复杂度 $O(n)$；
所有测试用例的 $n$ 之和不超过 $2 \times 10^5$，总时间绰绰有余。

## 实现要点

- **答案要开 `long long`**。$n = 10^5$ 时答案能达到 $5 \times 10^{13}$ 量级（例如
  $h = [1, 10^9, 1, 10^9, \dots]$ 这种"偶低奇高"的形状，每个偶数位置的代价都是 $10^9-1$ 量级），
  `int` 会溢出。
- **$c_i$ 用 `long long` 算**：$\max(h_{i-1}, h_{i+1}) + 1$ 最大到 $10^9 + 1$。
- 偶数 $n$ 的枚举里 $j$ 从 $0$ 到 $k$，$suf$ 的下标最大是 $2k+3 = n+1$，
  数组要开到 $n+2$，并把 `suf[n+1] = suf[n+2] = 0` 作为哨兵。
- 偶数 $n$ 时不能只比较"全取偶位置"和"全取奇位置"两组：
  最优集合常常需要在中途切换一次奇偶（见下面"数据设计说明"里的错解 A）。
- $n$ 为奇数时方案唯一，可以直接求和，不必走枚举。

## 参考实现

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

// 城市天际线（CF1706C）：
//   cost[i] = max(0, max(h[i-1], h[i+1]) + 1 - h[i]) —— 让第 i 栋变酷需要加盖的层数
//   （各个位置的加盖量互不影响：第 i 栋只需比原来左右两栋高，不必管别的楼房被加盖了多少）。
// 酷的楼房两两不相邻，且只有第 2 ~ n-1 栋可能变酷，所以酷楼房的数量最多是
//   k = floor((n-1)/2)：
//     n 为奇数时只有 {2, 4, ..., n-1} 这一种方案；
//     n 为偶数时记 k = n/2 - 1，偶位置 E = {2, 4, ..., n-2}、奇位置 O = {3, 5, ..., n-1}
//     各有 k 个，任何大小为 k 的合法集合都是「E 的前 j 个」并上「O 的后 k-j 个」，
//     所以枚举 j = 0..k 取最小值即可。

const int MAXN = 100000;                     // 单组 n 的上限
const long long MAXH = 1000000000LL;         // 层数上限 10^9

int n;
long long h[MAXN + 5];
long long costAt[MAXN + 5];                  // costAt[i]：让第 i 栋变酷需要加盖的层数
long long pre[MAXN + 5];                     // pre[i]：≤ i 的偶数位置的 costAt 之和
long long suf[MAXN + 5];                     // suf[i]：≥ i 的奇数位置的 costAt 之和

// 让第 i 栋楼房严格高于原来的左右两栋所需加盖的层数
long long coolCost(int i)
{
    long long need = max(h[i - 1], h[i + 1]) + 1;
    if (need <= h[i])
        return 0;
    return need - h[i];
}

long long solve()
{
    for (int i = 2; i <= n - 1; i++)
        costAt[i] = coolCost(i);

    // pre[i]：偶数位置 2, 4, ... 里不超过 i 的那些位置代价之和
    pre[0] = 0;
    pre[1] = 0;
    for (int i = 2; i <= n + 1; i++)
    {
        pre[i] = pre[i - 1];
        if (i <= n - 1 && i % 2 == 0)
            pre[i] += costAt[i];
    }

    // suf[i]：奇数位置 3, 5, ... 里不小于 i 的那些位置代价之和
    suf[n + 1] = 0;
    suf[n + 2] = 0;
    for (int i = n; i >= 1; i--)
    {
        suf[i] = suf[i + 1];
        if (i <= n - 1 && i >= 2 && i % 2 == 1)
            suf[i] += costAt[i];
    }

    if (n % 2 == 1)
        return pre[n - 1];                   // 奇数 n：唯一方案就是全部偶数位置

    // 偶数 n：取「偶数位置的前 j 个」与「奇数位置的后 k-j 个」，一共恰好 k 个
    int k = n / 2 - 1;
    long long ans = -1;
    for (int j = 0; j <= k; j++)
    {
        long long total = pre[2 * j] + suf[2 * j + 3];
        if (ans < 0 || total < ans)
            ans = total;
    }
    return ans;
}

int main()
{
    // 按题面要求使用文件 IO（见 docs/contest-conventions.md §2）；
    // 输出用 "wb"，保证在 Windows 上本地跑也不会写出 CRLF
    freopen("city.in", "r", stdin);
    freopen("city.out", "wb", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> h[i];
        cout << solve() << "\n";
    }
    return 0;
}
```

## 子任务说明

| 子任务 | 分值 | 说明 |
| --- | --- | --- |
| 1 | 30 | $n \le 8$ 且 $t \le 20$：可以直接枚举所有两两不相邻的位置集合 |
| 2 | 30 | $n$ 为奇数且 $t \le 50$：最优位置集合唯一，就是 $2, 4, \dots, n-1$ |
| 3 | 40 | 无额外限制：要处理 $n$ 为偶数的"中途切换一次奇偶"的情形 |

# 一二数组 · 题解

## 1. 思路

数组里只有 $1$ 与 $2$，记当前**总和**为 $S$，当前所有取值为 $1$ 的位置里最左的是 $L$、最右的是 $R$。

对询问 $s$：

1. $s > S$：显然不可能，`NO`；
2. $s$ 与 $S$ **奇偶性相同**：一定可以。因为把任意一个和为 $S'$ 的区间去掉它左边或右边的一个 $2$，
   就得到和为 $S' - 2$ 的区间；反复这样能把和一步步减到 $s$（$s$ 与 $S$ 同奇偶、且 $s \le S$）；
3. $s$ 与 $S$ 奇偶性不同：必须丢掉"奇数个 $1$"。丢得越少剩下的和越大，所以只需看两种最省的丢法：
   - 丢掉前缀 $[1, L]$，剩下的后缀和为 $S - (2L - 1)$；
   - 丢掉后缀 $[R, n]$，剩下的前缀和为 $S - (2(n - R) + 1)$。

   只要 $s$ 不超过这两者中较大的那个，并且奇偶性与它相同（这两个剩下的和的奇偶性都恰好与 $S$ 相反），
   就 `YES`；否则 `NO`。若数组里没有 $1$，则只能凑出偶数，直接 `NO`。

用 `set` 维护所有 $1$ 的位置即可在 $O(\log n)$ 内回答、修改同样是 $O(\log n)$。

## 2. 复杂度

每个测试用例 $O(n + q\log n)$，所有测试用例合计 $O(\sum n + \sum q \log n)$；空间 $O(n)$。

## 3. 实现要点

- 文件 IO：`ones.in` / `ones.out`，输出用 `"wb"`。
- 修改操作要同步更新总和 $S$ 与 `set`（先把旧的 $1$ 位置删掉，再按新值插入）。
- 输出必须与样例一致地写 **大写** `YES` / `NO`（评测逐字符比较）。
- 多组数据：每组的 `set` 与总和都要重新初始化。

## 4. 参考程序（与 `src/std.cpp` 一致）

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

const int MAXN = 100000; // 单个测试用例的数组长度上限

int n, q;
int a[MAXN + 5];     // a[1..n]：数组，每个元素是 1 或 2
int sumAll;          // 当前数组的元素之和
set<int> posOne;     // 当前所有取值为 1 的位置（下标从 1 开始）

// 当前数组里是否存在元素和恰好为 s 的连续子数组
bool canMake(int s)
{
    if (s > sumAll)
        return false;
    if ((sumAll - s) % 2 == 0) // 与总和同奇偶：一定能凑出来
        return true;
    if (posOne.empty())
        return false; // 全是 2：只能凑出偶数
    int first = *posOne.begin(); // 最左边那个 1 的位置
    int last = *posOne.rbegin(); // 最右边那个 1 的位置
    // 奇偶不同：必须丢掉一段含"奇数个 1"的前缀或后缀。丢得越少剩下的和越大，
    // 所以只需比较"丢掉前缀 [1, first]"（和 2*first-1）与"丢掉后缀 [last, n]"
    // （和 2*(n-last)+1）这两种最省的丢法。
    long long drop = min(2LL * first - 1, 2LL * (n - last) + 1);
    return s <= sumAll - drop;
}

int main()
{
    // 文件 IO：从 ones.in 读入、输出到 ones.out（wb 保证不写出 CRLF）
    freopen("ones.in", "r", stdin);
    freopen("ones.out", "wb", stdout);

    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &q);
        sumAll = 0;
        posOne.clear();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            sumAll += a[i];
            if (a[i] == 1)
                posOne.insert(i);
        }
        for (int k = 1; k <= q; k++)
        {
            int op;
            scanf("%d", &op);
            if (op == 1)
            {
                int s;
                scanf("%d", &s);
                printf("%s\n", canMake(s) ? "YES" : "NO");
            }
            else
            {
                int i, v;
                scanf("%d%d", &i, &v);
                if (a[i] != v)
                {
                    sumAll += v - a[i]; // 1 与 2 之间只会差 1
                    if (v == 1)
                        posOne.insert(i);
                    else
                        posOne.erase(i);
                    a[i] = v;
                }
            }
        }
    }
    return 0;
}
```

## 5. 子任务说明

| 子任务 | 测试点 | 限制 | 想放过的写法 |
| :---: | :---: | :--- | :--- |
| 1 | 1 ~ 6 | $n, q \le 2000$ | 每次询问枚举所有子数组（$O(nq)$） |
| 2 | 7 ~ 12 | **没有修改操作** | 静态数组：前缀和 + 双指针/前缀集合，不用管修改 |
| 3 | 13 ~ 20 | 无额外限制，$\sum n$ 与 $\sum q$ 都卡满 $10^5$ | 正解；必须 $O((n+q)\log n)$ |
# 生长之树 题解

## 题意要点

树一开始只有 1 号点，每个点上的数是 $0$。$q$ 次操作：

- `1 v`：给当前大小为 $sz$ 的树添加一个新点，编号 $sz+1$，它上面的数是 $0$；
- `2 v x`：给 $v$ 的子树（$v$ 自己 + 操作执行时已经存在的后代）里每个点加上 $x$。

**容易被读错、但样例 1 第一组数据明确排除了的一点**：新点上的数是 $0$，它**不会**继承它出现之前
那些"给祖先的子树加值"的操作；反过来，一次操作二只影响它执行时已经存在的点，之后才出现的点不算。
下面这份样例的推算可以验证这一点：

| 操作 | $1$ 号点 | $2$ 号点 | $3$ 号点 | $4$ 号点 | $5$ 号点 |
| --- | --- | --- | --- | --- | --- |
| 初始 | 0 | — | — | — | — |
| `2 1 3` | 3 | | | | |
| `1 1` | 3 | 0 | | | |
| `2 2 1` | 3 | 1 | | | |
| `1 1` | 3 | 1 | 0 | | |
| `2 3 2` | 3 | 1 | 2 | | |
| `1 3` | 3 | 1 | 2 | 0 | |
| `2 1 4` | 7 | 5 | 6 | 4 | |
| `1 3` | 7 | 5 | 6 | 4 | 0 |
| `2 3 2` | 7 | 5 | 8 | 6 | 2 |

最后一行就是题面里的 `7 5 8 6 2`。注意第 7 步 `2 1 4` 并没有把第 8 步才出现的 $5$ 号点算进去
（如果算进去，$5$ 号点会变成 $6$，与样例不符）。

## 每个点的最终值是什么

设点 $v$ 是第 $k$ 次操作一新建出来的（$k=0$ 表示 $v$ 是根）。$v$ 的最终值等于

$$
\sum_{\substack{\text{操作 } j \text{ 是操作二}\\ \text{且 } u_j \text{ 是 } v \text{ 的祖先或 } v \text{ 自己}\\ \text{且 } t_j < t_v}} x_j ,
$$

其中 $t_j$ 是操作 $j$ 的时刻、$t_v$ 是 $v$ 出现的时刻。也就是说：**只看那些"在 $v$ 出现之前"执行、
并且作用在 $v$ 的祖先上的操作二**。子树的形状一旦确定就不会变（$v$ 的后代只可能是之后才出现的点，
而它们不影响 $v$ 自己的值），所以"$u_j$ 是 $v$ 的祖先"用最终树判断就没问题，
需要在线判断的只有"$t_j < t_v$"这一件事。

## 做法

### 子任务 1（$q \le 2000$）：直接模拟

每次操作二就着当前的树真的遍历一遍 $v$ 的子树并加 $x$。单次代价是子树大小，$q$ 小的时候总代价
最多约 $2000 \times 2000 = 4 \times 10^6$，随便过。复杂度 $O(q^2)$。

### 子任务 2（所有加点都在所有加值之前）：建完树做一次 dfs

此时树在第一次操作二之前就已经定型：设点 $u$ 上被加了 $add_u$（把所有操作二的 $x$ 按 $u$ 累加），
那么从根往下走一遍，用 $cur$ 带着"根到当前点这条链上累加到的和"：

$$
ans_v = cur_v = cur_{parent(v)} + add_v .
$$

一遍 dfs 求出所有点的答案，$O(n)$。

### 满分做法：Euler 序 + 树状数组（按输入顺序扫一遍）

1. 先把**最终**的树建出来：第 $k$ 次操作一新建的点编号就是 $1+k$，所以按操作顺序读到 `1 v` 时
   直接把新点挂到 $v$ 上即可（这个编号恰好就是它在最终树里的编号）。
2. 对最终树求一遍 dfs 序。子树在 dfs 序里是一段连续的区间 $[in_v, out_v]$。
3. 按输入顺序再扫一遍操作，用一个支持"区间加、单点求值"的树状数组（差分 + 前缀和）维护
   "当前每个位置上累计被加了多少"：
   - `2 v x`：给 $[in_v, out_v]$ 整体加 $x$；
   - `1 v`（新点是 $u$）：此时树状数组里 $in_u$ 处的单点值，正是"在 $u$ 出现之前执行过、
     并且覆盖到 $u$ 的那些操作二"之和。因为 $u$ 出现之前它是空的（值为 $0$），这部分值必须扣掉。
     记 `start[u]` 为这个单点值即可。
4. 最后每个点的答案是 `bit.query(in_v) - start[v]`。

第 3 步为什么要"再扫一遍"：建树时已经把最终树定下来了，但树状数组上的加值必须按真实时间顺序发生，
这样新点出现时才能把它"出现之前"已经累计的部分记下来并从最终结果里扣掉。

复杂度：建树 + dfs + $q$ 次树状数组操作，$O(q \log q)$ 每组，空间 $O(q)$。

也可以用另一种等价写法：把操作**倒着**扫一遍。倒扫时"操作二给 $v$ 的子树区间加 $x$"、
"操作一新建的点 $u$ 在这一刻单点求值"就正好得到 $u$ 的最终答案（倒着扫时，先处理的是更晚的操作，
正好只把 $u$ 出现之后的加值算进去；根最后再查一次）。两份实现都在下面复核过。

### 实现要点

- **不能写递归 dfs**：$q$ 可以取到 $5\times10^5$，数据里有一条 $5\times10^5$ 个点的链，
  递归深度会爆栈。标程用显式栈（`std::vector<int>` 当栈，用负号标记"出栈"）。
- **所有测试用例的 $q$ 之和不超过 $5\times10^5$**，所以每组重建数组的开销按组清零即可；
  标程用全局数组 + 每组重置用到的部分。
- **答案会超过 32 位**：一个点最多被 $5\times10^5$ 次操作各加 $10^9$，达到 $5\times10^{14}$，
  必须用 `long long`。
- 输入规模到 $5\times10^5$ 行、$1.5\times10^6$ 个整数，加 `ios::sync_with_stdio(false); cin.tie(0);`。

## 参考实现

70 分代码，把暴力枚举用数据结构优化就能满分了。

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Ev
{
    // 1：对 v 增加子节点，增加的点编号是 x
    // 2：对 v 子树增加 x
    int op, v, x;
};
int q;
Ev ev[500000 + 5];
vector<int> e[500000 + 1 + 5];
int dfs_now, dfn[500000 + 5], siz[500000 + 5];
void dfs(int u)
{
    dfn[u] = ++dfs_now;
    siz[u] = 1;
    for (int v : e[u])
    {
        dfs(v);
        siz[u] += siz[v];
    }
}
long long start[500000 + 5]; // 存每个点加入的时候，他已经达到的大小
long long w[500000 + 5];     // 每个点的大小
void work()
{
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> ev[i].op >> ev[i].v;
        if (ev[i].op == 2)
            cin >> ev[i].x;
    }
    int tot = 1;
    for (int i = 1; i <= q; i++)
    {
        if (ev[i].op == 1)
        {
            tot++;
            e[ev[i].v].push_back(tot);
            ev[i].x = tot;
        }
    }
    dfs_now = 0;
    dfs(1); // dfs 序处理完
    for (int i = 1; i <= q; i++)
    {
        if (ev[i].op == 1)
        {
            int now = ev[i].x; // 新加的点
            start[dfn[now]] = w[dfn[now]];
            // cout << ev[i].x << "#" << w[ev[i].x] << "\n";
        }
        if (ev[i].op == 2)
        {
            // 子树 ev[i].v 对应的区间暴力修改
            int now = ev[i].v;
            for (int j = dfn[now];
                 j <= dfn[now] + siz[now] - 1;
                 j++)
                w[j] += ev[i].x;
            // cout << ev[i].v << "@" << ev[i].x << "\n";
            // for(int i=1;i<=tot;i++)
            //     cout<<w[i]<<",";
            // cout<<"\n";
        }
    }
    for (int i = 1; i <= tot; i++)
        cout << w[dfn[i]] - start[dfn[i]] << " ";
    cout << "\n";
    for (int i = 1; i <= tot; i++)
        e[i].clear(), w[i] = 0;
}
signed main()
{
    freopen("grow.in", "r", stdin);
    freopen("grow.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
        work();
    return 0;
}
```

## 子任务说明

| 子任务 | 分值 | 说明 |
| --- | --- | --- |
| 1 | 30 | $q \le 2000$：每次操作二真的遍历一遍子树，$O(q^2)$ 也能过 |
| 2 | 30 | 所有加点操作都在加值操作之前：树在第一次加值前就定型，建完树做一次 dfs 即可 |
| 3 | 40 | 无额外限制，$\sum q$ 卡满 $5\times10^5$，含链、菊花、随机父亲树与加点/加值交错的点 |

# 异或树 题解

## 思路

以 $1$ 为根，记 $b_v$ 为根到 $v$（含两端）路径上所有数的异或和。

对一条简单路径 $u \to v$，设 $w = \operatorname{lca}(u,v)$。$b_u \oplus b_v$ 把
$w \to u$ 与 $w \to v$ 两段上的点各算了一次，而 $a_w$ 一次也没算，
所以

$$b_u \oplus b_v = \bigl(\text{路径 } u\to v \text{ 上所有数的异或和}\bigr) \oplus a_w .$$

于是

$$u \to v \text{ 的权为 } 0 \iff b_u \oplus b_v = a_w .$$

上式对 $u = w$（路径的端点之一就是 $w$）同样成立，此时变成 $b_w \oplus b_v = a_w$。

**为什么"能改上面的点就改上面的点"不吃亏。** 把 $a_v$ 改成 $a'_v$ 后，$v$ 子树里每个点的
$b$ 值都同时异或上 $\delta = a_v \oplus a'_v$。于是：

- 两端都在 $v$ 的**同一个**儿子子树内、$w$ 严格低于 $v$ 的路径，两个端点各被异或一次
  $\delta$，$\delta \oplus \delta = 0$，**权不变**；
- 所有 $\operatorname{lca}$ 恰好是 $v$ 的路径**一定经过** $v$，改 $a_v$ 可以一次把它们全部破坏：
  例如把 $a_v$ 换成 $2^{30+i}$ 这样互不相同的"高位" $2$ 的幂，任何含 $v$ 的路径权里都会
  带上这个高位（若干个不同高位 $2$ 的幂异或起来仍不为 $0$，低位部分都 $< 2^{30}$），
  于是权必不为 $0$。

所以自底向上贪心：某个点 $v$ 上只要还存在"$\operatorname{lca}$ 为 $v$"的权为 $0$ 的路径，
就操作 $v$ 一次（而不是去操作更低处的点），这样不会比最优解差。

**如何快速判断。** 自底向上维护集合 $S_v$：$v$ 子树内**还没有被切断**的点的 $b$ 值。
处理 $v$ 时：

1. 把各个儿子的集合**启发式合并**（小集合并进大集合，每个元素最多被搬动 $O(\log n)$ 次）；
2. 合并过程中，对每个即将插入的元素 $x$，检查 $x \oplus a_v$ 是否已经在**别的儿子**的集合里
   —— 存在就说明有一条 $\operatorname{lca} = v$、权为 $0$ 的路径；
3. 再单独检查 $b_v \oplus a_v$ 是否在合并后的集合里（对应路径的一个端点是 $v$ 自己）；
4. 若发现这样的路径，答案加一，并**清空这个集合**：$v$ 被改过之后，$v$ 子树里任何走到
   子树外的路径都经过 $v$，已经被这次操作破坏，这些 $b$ 值不需要（也不应该）再往上传递；
5. 否则把 $b_v$ 也插入集合，连同集合一起交给父亲。

注意第 2 步只能比较**不同儿子**里的点：同一个儿子内部的两个点 $\operatorname{lca}$ 更低，
对应的路径在这一步并不归 $v$ 管。因此实现时要把"比较"和"插入"分成两遍做。

## 算法与复杂度

- 时间：启发式合并下每个元素最多被搬动 $O(\log n)$ 次，哈希表插入/查询均摊 $O(1)$，
  总期望 $O(n \log n)$（把哈希表换成 `std::set` 是 $O(n\log^2 n)$）。
  实测（含读入与进程启动）：标程在每个满规模测试点上都不超过 0.35s，
  换成 `std::set` 的另一份实现也不超过 0.7s，时限 3s 有充足余量。
- 空间：$O(n)$。
- 注意：$n$ 可以是一条 $2\times 10^5$ 个点的链，**不能写递归的 dfs**（会爆栈），
  标程用 bfs 序的逆序处理。

## 实现要点

- **集合的所有权**：每个点用一个 `unordered_set<int>*`，小集合合并进大集合后立刻
  `delete`，否则内存会被反复复制撑大。
- **比较与插入分两遍**：先扫一遍小集合做冲突检查，再整体插入；若边查边插，
  同一个儿子内部的两个点会被误判成冲突，答案会偏大。
- **别忘了清空**：发现冲突后必须把集合作废（`alive[v] = NULL`），
  否则子树里的 $b$ 值继续往上走，祖先会重复计数。
- **两个端点是同一点的情况**：检查 $b_v \oplus a_v$ 时要先合完所有儿子再查。
- $b_v < 2^{30}$（每个 $a_i < 2^{30}$），所以一切用 `int` 就够，答案 $\le n$。
- 读入量 $2\times10^5$ 个点、$2\times10^5$ 条边，加 `ios::sync_with_stdio(false); cin.tie(0);`。

## 参考实现

与 `problems/d3s3/src/std.cpp` 完全一致（文件 IO：`tree.in` / `tree.out`）。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n;
int a[MAXN + 5];
vector<int> e[MAXN + 5];
int sum[MAXN + 5];     // 根节点到每个点的点权异或和
set<int> se[MAXN + 5]; // 每个子树还要处理的点/当前树之前的点
int ans;
void dfs(int u, int fa)
{
    se[u].insert(sum[u]); // 直接存点的编号
    bool flag = false;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum[v] = sum[u] ^ a[v];
        dfs(v, u);
        // 启发式合并，永远保持 e[u] 是较大的
        if (se[v].size() > se[u].size())
            swap(se[u], se[v]);
        // 检查 v 里面哪些点会构成异或和为 0 的路径
        for (int now : se[v])
            if (se[u].find(now ^ a[u]) != se[u].end())
                flag = true; // 找到了
        for (int now : se[v])
            se[u].insert(now);
    }
    if (flag)
        ans++, se[u].clear();
}
int main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ans = 0;
    sum[1] = a[1];
    dfs(1, 0);
    cout << ans;
    return 0;
}

```

## 子任务说明

| 子任务 | 分值 | 说明 |
| --- | --- | --- |
| 1 | 30 | $n \le 8$：可以枚举"要改哪些点"的所有子集做判定 |
| 2 | 30 | $n \le 2000$：不做启发式合并、每个点老老实实合并儿子的集合也能过 |
| 3 | 40 | $n \le 2\times10^5$：必须启发式合并（链、深树的数据会卡掉 $O(n^2)$ 的合并） |