P17851 「RiOI-(-2)」houran 和芒果 / [ROI 2026 Day1] 泰莫利亚的调查 加强版
前言
这题的黑我觉得一部来是来自于这困难的卡常。那严苛的卡常几乎要了我的命
题面
有一棵 n 个节点有边权的树，边权为 \(w'_i (2 \le i \le n)\)，问最多 \(m\) 条不重合（没有共同端点）的链覆盖的边权最大是多少？
T 组询问，每次给 \(X_0,X_1,X_2,X_3\) 每次询问就是在边权为 \(w_i \gets w'_i \oplus x_{i \mod 4}\)，\(\oplus\) 表示按位异或。
- \(1\le m\le n\le 2\times 10^5\)；
- \(1\le f_i；
- \(0\le w_i,X_0,X_1,X_2,X_3<2^{17}\)；
- \(1\le T\le 256\)。
思路
暴力
显然的，每条链一定是从叶子往上走。
考虑一种错误的直接贪心：看每个点现在选了最大有多少，每次选最大的点出来暴力往父亲走，走到 \(u\) 相当于给 \(v \in son(u)\) 的子树内的叶子减去 \(w_v\)。
发现，本质是一个点选最大的儿子连上，而错误的情况显然就是某一点应该连向另一子树。有些人发现这可以 dp（比如赛时的我），但是那样我不会优化，所以我们可以考虑反悔贪心。相当于在选了的点 \(u\) 下面的 \(x \in son(u)\) 和本来选的 \(y\) 中的子树可以的贡献可以多出 \(w_x-w_y\)。最后用 ds 来优化可以做到 \(O(Tn\log{n})\)。
优化
考虑 max 非常难以处理，可以用一种 Trick 转化。
考虑一种检测器，对于一个 u，比如说它有 \(4\) 个儿子，称它是 \(1,2,3,4\)，可以假设 \(w_1 \le w_2 \le w_3 \le w_4\)，那么：
- 选了 \({1,2,3,4}\) 其中之一时，权值加上 \(w_1\)
- 选了 \({2,3,4}\) 其中之一时，权值加上 \(w_2-w_1\)
- 选了 \({3,4}\) 其中之一时，权值加上 \(w_3-w_2\)
- 选了 \({4}\) 其中之一时，权值加上 \(w_4-w_3\)
然后我们发现这样子是可以正确统计的，比如说选 \({1,3}\) 那么贡献就是 \(w_1+(w_2-w_1)+(w_3-w_2)=w_3\)，成功拿到了最大值。所以我们可以将检测器转化成虚点，将边权变为虚点点权，就变成从叶子到根的带权路径和最大。还是这个例子我们可以转化成
u\1'(w_1)/ \1 2'(w_2-2_1)/ \2 3'(w_3-w_2)/ \3 4'(w_4-w_3)/4
转成带权路径和就是模板了，就是重链剖分，每个点选择所在链值最大的儿子作为重儿子，然后贪心地选择最大的链逐个选择即可（读者自证不难）。
因为每个点最多只需要一个虚点作为父亲，所以还是 \(O(n)\) 个点，用 nth_element 可以将统计答案优化到 \(O(n)\)，用基数排序也是 \(O(n)\)，所以总时间复杂度为 \(O(n)\)。
卡常
因为 \(O(Tn\log{n})\) 的常数非常小，所以此题时限非常紧，所以需要很多卡常，以下卡常技巧按效果从大到小排。
- 递归改迭代，因为 \(fa_i，所以可以直接用循环代替递归
- 在人少的时候交，用 c++23 或 c++20 交。非必须的，循环可以写成可以被自动向量化的形式
- 所有点排成一个数组以 \(fa_i\) 为第一关键字，\(w_i\) 为第二关键字（可以拆开高低九位）排序，然后每个点的儿子就是数组上连续的一个区间，省掉了一个
vector；其实也可以放数组上，然后每次只对于每个同样的父亲的连续段来排序，少的用sort，大的用基排 - 建完的虚点是一棵二叉树，可以只存左右儿子，省掉一个
vector - 接着上一个，虚点直接对应实点，在枚举时直接把实点和虚点放到一起处理，每个点都最多只有一个虚点和一个实点作为儿子，所以只需要记连向虚点的边即可
- 仔细开
ll，只有链的值和答案统计要开ll，\(w\) 和点权等则只需要int
::::success[ugly code]
#include
using namespace std;
typedef long long ll;
typedef long double ld;
#define freop(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define endl '\n'
#define inf 0x7f7f7f7f
#define lb(x) ((x)&-(x))
#define pii pair
#define fir first
#define sec second
#define mkp make_pair
const int N=2e5+5,M=4e5+5,V=(1<<17),R=(1<<9)-1;
int T,m,n,fat[N],son[M],nxt[M],ow[N],w[N],nw[N],x[4],g[N],t[N],cnt[N];
int cs[N],mx;
ll sm[N],ans;inline bool cmp(int x,int y){return w[x]>9];for(int i = 0,sm=l;i<=R;++i)sm+=cnt[i],cnt[i]=sm-cnt[i];for(int i = l;i<=r;++i)g[cnt[w[t[i]]>>9]++]=t[i];
}
inline void sorts(){int i=2,j=2;while(i<=n){while(fat[g[i]]==fat[g[j]]) ++j;// cerr << i << ' ' << j-1 << endl;if(j-i<=256) sort(g+i,g+j,cmp);else ss(i,j-1);i=j;}
}
inline void build(){for(int i = n,u=g[n];i>1;u=g[--i]){if(fat[g[i-1]]^fat[u]) nxt[fat[u]]=u+n,nw[u]=w[u];else nxt[g[i-1]+n]=u+n,nw[u]=w[u]-w[g[i-1]];}
}
inline void find(){for(int i = n,u=g[n];i>1;u=g[--i]){int l=son[nxt[u]],r=son[nxt[u+n]];if(!nxt[u]) son[u+n]=l=u;sm[son[u+n]=(sm[l]>sm[r]?l:r)]+=nw[u];}
}int main(){cin.tie(0)->ios::sync_with_stdio(false);cout.tie(0);sm[0]=-1;// freop("mango");
//↑以上为初始化↑
//------------------------------cin >> n;for(int u = 2;u<=n;++u)cin >> fat[u],mx=max(mx,++cs[fat[u]]);for(int i = 1;i<=n;++i) ++cnt[fat[i]];for(int i = 0,sm=1;i<=n;++i)sm+=cnt[i],cnt[i]=sm-cnt[i];for(int i = 1;i<=n;++i)g[cnt[fat[i]]++]=i;g[1]=0;for(int i = 2;i<=n;++i) cin >> ow[i];cin >> T;while(T--){cin >> x[0] >> x[1] >> x[2] >> x[3] >> m;for(int i = 2;i<=n;++i) sm[i]=0,w[i]=ow[i]^x[i%4];for(int i = 1;i<=(n<<1);++i) son[i]=nxt[i]=0;ans=sm[1]=0,sorts(),build(),find();// for(int i = 1;i<=n*2;++i) cerr << g[i] << ' ';cerr << endl; nth_element(sm+1,sm+m+1,sm+n+1,greater());for(int i = 1;i<=m;++i) ans+=sm[i];cout << ans << endl;}return 0;
}
::::