BZOJ_5338_ [TJOI2018]xor_可持久化trie
Description
有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并
将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
Input
第一行两个整数N,K。
接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。
输入保证所有点之间是联通的。
N<=2000,0<=K<=N
Output
输出一个正整数，表示收益的最大值。
Sample Input
5 2
1 2 3
1 5 1
2 3 1
2 4 2
1 2 3
1 5 1
2 3 1
2 4 2
Sample Output
17
【样例解释】
将点1,2染黑就能获得最大收益。
【样例解释】
将点1,2染黑就能获得最大收益。
HINT
2017.9.12新加数据一组 By GXZlegend
博客里没有几道可持久化trie的题，还是更一篇吧。
同时要求子树和两点路径上的信息，
只能用两个序维护一下，然后可持久化一下随便搞搞。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 200050
int head[N],to[N],nxt[N],val[N],cnt,n,m,be[N],ed[N],tot,root[N],t[N*33],sanae,ch[N*33][2],son[N],siz[N],fa[N],dep[N],top[N];
int t2[N*33],ch2[N*33][2],dfn[N],marisa,reimu,root2[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void update(int x,int c,int &y,int q) {
y=++sanae; int p=y; t[p]=t[q]+c;
int i;
for(i=30;i>=0;i--) {
int k=(x>>i)&1;
ch[p][k]=++sanae; ch[p][!k]=ch[q][!k];
p=ch[p][k]; q=ch[q][k]; t[p]=t[q]+c;
}
}
void upd(int x,int c,int &y,int q) {
y=++reimu; int p=y; t2[p]=t2[q]+c;
// printf("upd---%d %d %d %d\n",p,q,t2[p],t2[q]);
int i;
for(i=30;i>=0;i--) {
int k=(x>>i)&1;
ch2[p][k]=++reimu; ch2[p][!k]=ch2[q][!k];
p=ch2[p][k]; q=ch2[q][k]; t2[p]=t2[q]+c;
}
}
void dfs(int x,int y) {
dfn[x]=++marisa; upd(val[x],1,root2[marisa],root2[marisa-1]);
// printf("dfs---%d %d %d %d\n",root2[marisa],root2[marisa-1],t2[root2[marisa]],t2[root2[marisa-1]]);
// printf("%d %d %d %d\n",t2[root2[1]],t2[root2[2]],t2[root2[3]],t2[root2[4]]);
int i; be[x]=++tot; update(val[x],1,root[tot],root[tot-1]); siz[x]=1; fa[x]=y; dep[x]=dep[y]+1;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x); siz[x]+=siz[to[i]]; if(siz[son[x]]<siz[to[i]]) son[x]=to[i];
}
}
ed[x]=++tot; update(val[x],-1,root[tot],root[tot-1]);
}
void dfs2(int x,int t) {
top[x]=t;
if(son[x]) dfs2(son[x],t);
int i;
for(i=head[x];i;i=nxt[i])if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
int lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]>dep[top[y]]) swap(x,y);
y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
int solve1(int x,int y,int v) {
// printf("%d %d %d %d\n",x,y,t2[x],t2[y]);
int i,re=0;
for(i=30;i>=0;i--) {
int k=!((v>>i)&1);
if(t2[ch2[y][k]]-t2[ch2[x][k]]) {
re+=(1<<i); x=ch2[x][k]; y=ch2[y][k];
}else x=ch2[x][!k],y=ch2[y][!k];
}
return re;
}
int solve2(int x,int y,int z,int w,int v) {
int i,re=0;
for(i=30;i>=0;i--) {
int k=!((v>>i)&1);
if(t[ch[x][k]]+t[ch[y][k]]-t[ch[z][k]]-t[ch[w][k]]>0) re+=(1<<i),x=ch[x][k],y=ch[y][k],z=ch[z][k],w=ch[w][k];
else x=ch[x][!k],y=ch[y][!k],z=ch[z][!k],w=ch[w][!k];
}
return re;
}
int main() {
scanf("%d%d",&n,&m);
int i,x,y,opt,z;
for(i=1;i<=n;i++) scanf("%d",&val[i]);
for(i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,0); dfs2(1,1);
// printf("%d %d %d %d\n",t2[root2[1]],t2[root2[2]],t2[root2[3]],t2[root2[4]]);
for(i=1;i<=m;i++) {
scanf("%d%d%d",&opt,&x,&y);
if(opt==1) {
// printf("%d\n",root2[dfn[x]-1]);
printf("%d\n",solve1(root2[dfn[x]-1],root2[dfn[x]+siz[x]-1],y));
}else {
scanf("%d",&z);
int l=lca(x,y);
printf("%d\n",solve2(root[be[x]],root[be[y]],root[be[l]],root[be[fa[l]]],z));
}
}
}