C. houran 和芒果（mango）
题目描述
给出一棵树，边有边权，你可以选出不超过 \(m\) 条链，满足链的两个端点有祖先后代关系，并且任意两条链不能有重复的点。你要最大化覆盖的边的边权和。
做法
有一个 \(\mathcal O(\sum nm)\) 的 dp，但是我不会优化，所以这里讲的是反悔贪心的做法。
由于一个点最多只能被一条链覆盖，那么 \(u\) 只能和一个儿子连边（这指的是在同一个链中，所以这条边会加进被覆盖的边集中），如果在满足链数限制的前提下有多个儿子可以连边，贪心选一个边权最大的边连接上是最优的，正是这一点导致了直接贪心不对，引出了反悔贪心。
将贪心想象为在一个装满金币的袋子里拿金币，贪心拿最大的几个，这种想法在金币之间互不影响的前提下是成立的，但是如果后面的金币的面值会受到前面拿出的金币的影响，贪心就是错的。而反悔贪心就是换了一种方式表示金币的面值，使其相互独立。反悔贪心的主要思想就是用拿出两枚金币的最大值 \(V_2\) 减去只拿出一枚金币的最大值 \(V_1\) 作为第二枚金币的面值，用 \(V_3-V_2\) 作为第三枚金币的面值，这样金币之间就相互独立了。
这一题反悔贪心的过程是这样的，先将每个点的儿子按照连向父亲的边权大小降序排序。然后自下而上地贪，假设当前处理 \(u\)，并且他的儿子已经处理好了，算出了一个以 \(v\) 为链顶的最长链的长度 \(f_v\)。从前往后扫，如果 \(f_v+w_v>f_u\)，这里 \(f_u\) 存的是前面访问过的儿子 \(f_p+w_p\) 的最大值，假设前面达成最大值的儿子是 \(p\)，那么给 \(p\) 发一张反悔票，\(f_p\leftarrow f_u-w_v\)，并 \(f_u\leftarrow f_v+w_v,f_v\leftarrow 0\)。对所有处理完之后使用贪心选最大的 \(m\) 个点的 \(f\) 值就是答案。
解释一下给 \(p\) 发反悔票是什么意思。就是选一个的时候 \(f_v+w_v\) 是最大的，然后如果在前面再选一个的时候，如果选了 \(v,p\)，那么答案是 \(f_v+f_p+w_p,w_p\geq w_v\)，而答案的增量恰好就是反悔票的大小，\(f_p+w_p-w_v\) 即 \(f_u-w_v\)。
但是这个为什么是对的呢？🤔
是这样的，选一个的时候，\(f_u\) 就是答案，然后如果选两个，即再选一个，那么在反悔票中，选上最大的那个会得到选两个的最大权值。假设第一个选的是 \(v_1\)，首先不会选 \(v_1\) 后面的反悔，因为 \(w_{v_1}\) 比后面的点的 \(w\) 大，选后面的反悔不如直接加上其 \(f\) 数组的值。在 \(v_1\) 之前的所有点中，假设 \(v_1\) 把反悔票发给了 \(v_2\)（即 dp 转移时 \(v_1\) 把 \(v_2\) 挤下去了，或者说 \(v_2\) 是 \(v_1\) 的上任冠军），则第二个选 \(v_2\) 反悔最优，这是因为反悔的增量为 \(f_v+w_v-w_{v_1}\)，第三项固定，而由 dp 转移可知 \(v_1\) 前，在 \(v_2\) 处 \(f_v+w_v\) 最大。而且也必然选到 \(v_2\)，因为 \(v_2\) 之前的反悔票一定小于 \(v_2\) 的反悔票，之前的 \(f_v+w_v\) 更小，反悔减的 \(w\) 更大。
同理选了 \(v_2\) 之后，选 \(v_2,v_1\) 之间的点反悔不如直接加上 \(f\) 值，所以不会出现找当前连向 \(u\) 的点的右边的点来反悔的情况，因此反悔票不发给这些点是正确的。这样就可以归纳论证。所以这个反悔贪心是正确的。这是把所有 \(u\) 的儿子的反悔操作单独提出来看，但是 \(u\) 儿子的反悔操作中间可能会穿插其他点的儿子反悔，但是他们相互独立，不会有影响。具体来说，不同子树中的选择选的链都不会相交，不会有影响。一个点要反悔，必须先选上第一个最大的 \(f_v+w_v\)，在同一棵子树内的，由于 \(f\) 数组的值从下往上肯定是只增不减的，必然是先选上面的才能选到下面的点，而第一个的贪心和后面的反悔，对下面的点来说都是选了一个最长链，因此一个点开始反悔的时候，第一步一定已经做好了。
这一题卡常，排序需要用计数排序。然后一个点存儿子的时候要存在一个连续的下标区间内，提高缓存命中率。选前 \(m\) 大的可以使用 nth_element。
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,Q,X[4];
int a[N],b[N],fa[N],lst[N];
int h[N],fi[N];
int bucket[(1<<17)+2],c[N];
ll f[N];int g[N];
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=2;i<=n;i++)cin>>fa[i],h[fa[i]]++;int sum=0;for(int i=1;i<=n;i++)fi[i]=sum+1,sum+=h[i];for(int i=2;i<=n;i++)cin>>b[i];cin>>Q;while(Q--){cin>>X[0]>>X[1]>>X[2]>>X[3]>>m;for(int i=2;i<=n;i++)a[i]=b[i]^X[i%4],bucket[a[i]]++;for(int i=1;i<1<<17;i++)bucket[i]+=bucket[i-1];for(int i=2;i<=n;i++)c[bucket[a[i]]--]=i;for(int i=1;i<=n;i++)lst[i]=0;for(int i=n-1;i>=1;i--){int u=c[i];h[fi[fa[u]]+lst[fa[u]]]=u;lst[fa[u]]++;}for(int u=n;u>=1;u--){f[u]=g[u]=0;for(int i=fi[u];i<(u==n?n+1:fi[u+1]);i++){int v=h[i];if(f[v]+a[v]>f[u])f[g[u]]=f[u]-a[v],f[u]=f[v]+a[v],g[u]=v,f[v]=0;}}nth_element(f+1,f+m,f+n+1,greater());ll ans=0;for(int i=1;i<=m;i++)ans+=f[i];cout<