3590. 第 K 小的路径异或和（平衡树+树上启发式合并） · znzryb
## 思路讲解
## AC代码
[https://leetcode.cn/problems/kth-smallest-path-xor-sum/submissions/642233568/](https://leetcode.cn/problems/kth-smallest-path-xor-sum/submissions/642233568/)
::: 源代码
```cpp
#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……）