luoguP6623 [省选联考 2020 A 卷] 树(trie树)

Luogu

题外话：

。。。想不出来啥好说的了。

我认识的人基本都切这道题了。

就我只会10分暴力。

我是傻逼。

题解时间

先不想用什么维护，拆分成如下操作：

插入，合并，全局异或和，全局加一。

全局加一咋做？

Trie树变成从低位到高位记录就好。

全局加一就是直接反转，看到进位(这一位存在1方向节点变成0方向节点)就递归下去继续反转。

然后就没了。

#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};

template<typename TP>inline void read(TP &tar)

{

	TP ret=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}

	tar=ret*f;

}

template<typename TP,typename... Args>inline void read(TP& t,Args&... args){read(t),read(args...);}

namespace RKK

{

const int N=530011;

struct sumireko{int to,ne;}e[N];int he[N],ecnt;

void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}

int n,v[N],fa[N];lint ans;

int rt[N],tcnt;

struct remilia{int d,s,v,son[2];}t[N<<5];

int merge(int x,int y)

{

	if(!x||!y) return x|y;

	t[x].s+=t[y].s,t[x].v^=t[y].v;

	t[x].son[0]=merge(t[x].son[0],t[y].son[0]);

	t[x].son[1]=merge(t[x].son[1],t[y].son[1]);

	return x;

}

void fuckup(int x)

{

	t[x].s=t[t[x].son[0]].s+t[t[x].son[1]].s;

	t[x].v=t[t[x].son[0]].v^t[t[x].son[1]].v;

	if(t[x].son[1]) t[x].v^=(t[t[x].son[1]].s&1)<<t[x].d;

}

void change(int x){swap(t[x].son[0],t[x].son[1]);if(t[x].son[0]) change(t[x].son[0]);fuckup(x);}

void insert(int x,int w)

{

	if(t[x].d==26) return (void)(t[x].s++);

	int &y=t[x].son[(w>>t[x].d)&1];

	if(!y) y=++tcnt,t[y].d=t[x].d+1;insert(y,w);

	fuckup(x);

}

void dfs(int x)

{

	rt[x]=++tcnt;

	for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to) dfs(t),rt[x]=merge(rt[x],rt[t]);

	change(rt[x]),insert(rt[x],v[x]),ans+=t[rt[x]].v;

}

int main()

{

	read(n);for(int i=1;i<=n;i++) read(v[i]);for(int i=2;i<=n;i++) read(fa[i]),addline(fa[i],i);

	dfs(1);printf("%lld",ans);

	return 0;

}

}

int main(){return RKK::main();}

巴特西

luoguP6623 [省选联考 2020 A 卷] 树(trie树)

luoguP6623 [省选联考 2020 A 卷] 树(trie树)

题外话：

题解时间

最新文章

热门文章