abc_437 部分题解

比赛链接

C Reindeer and Sleigh 2

问题陈述

有 $N$ 头驯鹿和一个雪橇。这只 $i$ 只驯鹿的重量是 $W _ i$ ，力量是 $P _ i$ 。

每只驯鹿可以选择 "拉雪橇 "或 "坐雪橇"。这里，拉雪橇的驯鹿的总力量必须大于或等于坐雪橇的驯鹿的总重量。最多可以有多少只驯鹿坐上雪橇？

给你 $T$ 个测试案例。请逐一解答。

限制因素

$1\leq T\leq 10^5$
$1\leq N\leq 3\times 10^5$
$1\leq W _ i,P _ i\leq 10^9$
所有输入值均为整数。
一个输入文件中 $N$ 的总和最多为 $3\times 10^5$ 。
输入

输入内容由标准输入法提供，格式如下

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$
$W_1$ $P_1$
$W_2$ $P_2$
$\vdots$
$W_N$ $P_N$

思路:对于每个人可以选择加入重量，也可以选择贡献拉力，因为这两个只能选一个那么，我们假设所有人都贡献拉力，我们可以得出一个等式，选着加入重量的人的重量和<=所有人的拉力-选着加入重量的人的拉力，移项之后等价于每个人选择上车的代价是自己的拉力和重量之和，于是我们可以按照自己的拉力和重量之和从小达到排序，我们最后不能超过全部拉力的大小即可。

AC代码：

cpp
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 3e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/
void solve()
{
    ll n;
    cin >> n;
    vector<PLL> s(n + 1, {0, 0});
    ll tot = 0;
    rep(i, 1, n) cin >> s[i].fi >> s[i].se, tot += s[i].se;
    sort(s.begin() + 1, s.end(), [&](const auto &a, const auto &b)
         { return a.fi + a.se < b.fi + b.se; });
    ll now = 0, ans = 0;
    rep(i, 1, n)
    {
        ll x = s[i].fi + s[i].se;
        if (now + x <= tot)
        {
            ans++;
            now += x;
        }
        else
        {
            break;
        }
    }
    cout << ans << endl;
}

int main()
{
    IOS;

    int _ = 1;
    cin >> _; // 如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

D Sum of Differences

问题陈述

给你一个长度为 $N$ 的正整数序列 $A = (A _ 1, A _ 2, \dots, A _ N)$ 和一个长度为 $M$ 的正整数序列 $B = (B _ 1, B _ 2, \dots, B _ M)$ 。

求 $\displaystyle \sum _ {i=1}^{N} \sum _ {j=1}^{M} |A _ i - B _ j|$ 的值，模为 $998244353$ 。

限制因素

$1 \leq N,M \leq 3 \times 10^5$
$1 \leq A _ i, B _ j < 998244353$
所有输入值均为整数。
输出

单行输出答案。

输入

输入内容由标准输入法提供，格式如下

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_M$

思路：看到这个题目暴力肯定是不可取的，[Ai-Bi]的结果都有绝对值，那么自然而然聪明一点的想法是拆开绝对值符号，算当前的Ai对答案的贡献，以及在当前Ai下Bi的贡献是多少，我们不难发现要想去绝对值改变符号的话，要求B数组中有大于当前Ai的数存在，在这个数之前的所有B数组都是负贡献，在此之后的B数组都是正贡献，那么A数组恰好相反，由于B数组的连续性，我们可以维护B数组的前缀和来优化算B数组的贡献，知道这些之后就是二分找出B数组大于当前A的索引，然后注意合理取模就好。

AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/

void solve()
{
    ll n, m;
    cin >> n >> m;
    vll a(n + 1, 0), b(m + 1, 0);
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) cin >> b[i];
    map<ll, ll> w;
    sort_range(a, 1, n);
    sort_range(b, 1, m);
    vll preb(m + 1, 0);
    rep(i, 1, m)
    {
        preb[i] = preb[i - 1] + b[i];
    }
    ll ans = 0;
    rep(i, 1, n)
    {
        ll x = a[i];
        auto it = upper_bound(b.begin() + 1, b.end(), x);
        if (it != b.end())
        {
            ll d = it - b.begin() - 1;
            ans = (ans + (x % Md3) * (((2 * d - m) % Md3 + Md3) % Md3) % Md3);
            ans = (ans - preb[d] % Md3 + Md3) % Md3;
            ans = (ans + (preb[m] - preb[d]) % Md3 + Md3) % Md3;
        }
        else
        {
            ans = (ans + (m * x) % Md3 + Md3) % Md3;
            ans = (ans - preb[m] % Md3 + Md3) % Md3;
        }
    }
    cout << ans << endl;
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

后续再补充一个手写二分的代码，容器的二分还是没那么习惯。

E Sort Arrays

问题陈述

有 $N+1$ 个序列 $A _ 0, A _ 1, \ldots, A _ {N}$ 。 $A _ i$ 的定义如下：

$A _ 0$ 是空序列。
$A _ i\ (1\leq i\leq N)$ 是在序列 $A _ {x _ i}\ (0\leq x _ i\lt i)$ 的末尾追加整数 $y _ i$ 得到的序列。

找出满足以下条件的 $(1,2,\ldots,N)$ 的排列 $P=(P _ 1, P _ 2,\ldots,P _ N)$ ：

就 $i = 1,2,\ldots,N-1$ 而言，以下条件之一成立：
- $A _ {P _ i}$ 在词序上小于 $A _ {P _ {i+1}}$ 。
- $A _ {P _ i}= A _ {P _ {i+1}}$ 和 $P _ i\lt P _ {i+1}$ 。

换句话说，当 $A _ 1,A _ 2,\ldots,A _ N$ 按词典顺序排列时（当有多个相等的序列时，先排列指数小的序列）， $P$ 是出现在该排列中的指数序列。

什么是序列的词典顺序？

如果以下两个条件之一成立，那么序列 $S = (S _ 1,S _ 2,\ldots,S _ {|S|})$ 在词法上**小于序列 $T = (T _ 1,T _ 2,\ldots,T _ {|T|})$ 。这里， $|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

$|S| \lt |T|$ 和 $(S _ 1,S _ 2,\ldots,S _ {|S|}) = (T _ 1,T _ 2,\ldots,T _ {|S|})$ 。
存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ ，使得下面两个条件都成立：
- $(S _ 1,S _ 2,\ldots,S _ {i-1}) = (T _ 1,T _ 2,\ldots,T _ {i-1})$
- $S _ i$ 在数值上小于 $T _ i$ 。
- 限制因素

$1\leq N\leq 3\times 10^5$
$0\leq x _ i\lt i$
$1\leq y _ i\leq 10^9$
所有输入值均为整数。
输入

输入内容由标准输入法提供，格式如下

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

题解：Sort Arrays (AtCoder E)

1. 题目大意

给定 $N$ 个序列的生成规则：$A_0$ 为空序列，对于 $1 \le i \le N$，$A_i$ 是在序列 $A_{x_i}$（$x_i < i$）的末尾追加一个整数 $y_i$ 得到的。
要求将 $A_1, A_2, \dots, A_N$ 按字典序排序。如果两个序列完全相等，则编号较小的排在前面。

2. 模型转化：树与字典树 (Trie)

由于 $A_i$ 是由 $A_{x_i}$ 派生而来的，这天然构成了一棵以 $0$ 为根节点的树：

节点与边：每个索引 $i$ 代表一个节点。父节点 $x_i$ 到子节点 $i$ 的边权为 $y_i$。
序列本质：序列 $A_i$ 就是从根节点 $0$ 到节点 $i$ 路径上所有边权的有序集合。
排序目标：对树上的所有节点（除 $0$ 外）进行一次符合字典序规则的遍历。

3. 核心规则与难点

前缀规则：若序列 $S$ 是 $T$ 的前缀，则 $S < T$。在树上表现为：父节点必须先于子节点输出。
数值规则：字典序比较时，数值 $y$ 越小的分支，优先级越高。
编号规则：如果多个节点生成的路径（序列）完全相同，则按节点的索引 $i$ 从小到大排序。

难点：当多个节点对应相同的序列时，它们在字典序上是“平级”的。如何将这些节点“合并”处理，并同时满足编号排序和后续分支的字典序比较？

4. 算法设计：层级合并 DFS

我们采用一种“按集合递归”的 DFS 策略，模拟在隐式字典树上的搜索过程。

DFS 函数定义：
void dfs(vector<int> &q)：其中 $q$ 存储的是当前所代表序列完全相等的节点编号集合。

执行步骤：

排序与输出：
对集合 $q$ 按编号从小到大排序并依次输出。由于 $q$ 中节点代表的是当前前缀相同的最短序列，这完美解决了“前缀规则”和“编号规则”。
收集子节点：
遍历 $q$ 中所有节点在链式前向星中的出边，收集所有一阶子节点，存入 vector<pair<int, int>> ch，格式为 {权值 y, 编号 id}。
双指针分组（核心）：
对 ch 按权值 $y$ 排序。利用双指针逻辑 for(i=0, j=0; ...; i=j)：
- 权值 $y$ 不同：代表不同的字典序分支，按 $y$ 从小到大的顺序处理。
- 权值 $y$ 相同：代表这些子节点在追加了相同的 $y$ 后，序列依然相等。将这些 $y$ 相同的编号提取到新的 vector<int> nxt 中。
递归向下：
对每个 nxt 集合调用 dfs(nxt)，继续处理下一位的字典序。

5. 复杂度分析

时间复杂度：$O(N \log N)$。
每个节点和每条边在全过程中只进入 $q$ 和 $ch$ 一次。主要的复杂度开销在于排序。全过程排序的摊还复杂度为 $O(N \log N)$。
空间复杂度：$O(N)$。
主要为链式前向星的存储开销和递归过程中临时 vector 的空间占用。

6. 总结

本题巧妙地将字典序排序转化为树形结构上的搜索。通过“集合传递”代替“单节点传递”，解决了序列相等时的状态合并问题，配合双指针分组逻辑，优雅地实现了对 Trie 树的隐式遍历。
大概就是这样，借助了一些大模型，主要是这个dfs的解释我解释的总是好绕。
另外我把我最原始的想法的代码给在后面。
AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 3e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/
int n;
int h[N], e[M], ne[M], w[M], idx;
// int fa[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(vector<int> &q)
{
    if (q.empty())
        return;
    sort(all(q));
    for (auto x : q)
        if (x)
            cout << x << " ";
    vector<PII> ch; //{权值，编号};
    for (auto u : q)
    {
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            ch.push_back({w[i], j});
        }
    }
    sort(all(ch));
    for (int i = 0, j = 0; i < ch.size(); i = j)
    {
        while (j < ch.size() && ch[j].fi == ch[i].fi)
            j++;
        vector<int> nxt;
        rep(k, i, j - 1) nxt.push_back(ch[k].se);
        dfs(nxt);
    }
}

void solve()
{
    mem(h, -1);
    cin >> n;
    rep(i, 1, n)
    {
        int x, y;
        cin >> x >> y;
        add(x, i, y);
    }
    vector<int> root = {0};
    dfs(root);
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

最初MLE的代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 3e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/
int n;
int h[N], e[M], ne[M], w[M], idx;
int fa[N];
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void solve()
{
    cin >> n;
    mem(h, -1);
    map<int, vector<int>> id;
    rep(i, 1, n)
    {
        int x, y;
        cin >> x >> y;
        fa[i] = x;
        // add(x, i, y);
        // add(i, x, y);
        id[i] = id[fa[i]];
        id[i].push_back(y);
    }
    map<vector<int>, vector<int>> mp;
    for (auto [id, tmp] : id)
    {
        mp[tmp].push_back(id);
    }
    for (auto [tmp, id] : mp)
    {
        for (auto &x : id)
            if (x != 0)
                cout << x << " ";
    }
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

这份代码有12个测试点MLE了，其实想法感觉没问题，只是dfs的复杂度我不是很会分析，一开始就没觉得边dfs边排序合并这样的复杂度是可以过的。

后续还有两个题目，基于目前水平和期末备考，F是一个线段树的题目，如果要写，要花大量的时间调试，再加上线段树不是很熟悉，如果要写要花大量的时间，但是收获的也许只是对线段树的维护更加熟练一些，并没有太多的启发的思考，就寒假的时候再把这篇题解补充完整。