3590. 第 K 小的路径异或和（平衡树+树上启发式合并）

思路讲解

AC代码

https://leetcode.cn/problems/kth-smallest-path-xor-sum/submissions/642233568/

源代码

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

class Solution {
public:
    vector<int> kthSmallest(vector<int>& par, vector<int>& vals, vector<vector<int>>& queries) {
        vector<vector<int> > g(par.size()+5);
        vector<vector<array<int,2> > > que(par.size()+5);
        for(int i=1;i<par.size();++i){
            g[par[i]].push_back(i);
        }
        for(int i=0;i<queries.size();++i){  // offline query
            que[queries[i][0]].push_back({queries[i][1],i});
        }
        vector<int> ans(queries.size());
        auto dfs=[&](auto &&self,int u,int val) -> ordered_set*{
            val^=vals[u];
            ordered_set* st=new ordered_set();
            st->insert(val);
            for(auto v:g[u]){
                ordered_set* t=self(self,v,val);
                // 启发式合并：小集合并入大集合
                if(t->size()>st->size()){
                    swap(st,t);
                }
                for (int k : *t) {
                    st->insert(k);
                }
                delete t;
            }
            for(auto &t:que[u]){
                int k=t[0],idx=t[1];
                if(k>st->size()){
                    ans[idx]=-1;
                    continue;
                }
                // 注意：k 是从 0 开始的
                ans[idx]=*st->find_by_order(k-1);
            }
            return st;
        };
        dfs(dfs,0,0);
        return ans;
    }
};

心路历程（WA，TLE，MLE……）