首页 > 其他分享 >#Trie#洛谷 6018 [Ynoi2010] Fusion tree

#Trie#洛谷 6018 [Ynoi2010] Fusion tree

时间:2024-05-10 17:22:06浏览次数:25  
标签:rt 洛谷 fa Trie 6018 int trie ans 节点

题目

给定一棵树,树上每个节点都有点权,需要实现三种操作,

第一种是将与 \(x\) 相邻的所有节点点权加一,第二种是单点减小点权,

第三种是查询与 \(x\) 相邻的所有节点点权的异或和


分析

相邻实际上就是父节点和子节点,不妨将其拆开考虑,

需要解决单点查询单点修改的问题,考虑维护 \(n\) 棵 Trie 求子节点异或和

由低位到高位建树,实际上 \(w=(w_0 \oplus w_1)\times 2+[cnt_1\ is\ odd]\)

加一实际上就是进位的问题,那么 \(1,11,111,\dots\) 结尾的数都会变成零,

实际上就是 \(trie[p][0]\) 和 \(trie[p][1]\) 的交换

然后 \(1\) 为根节点而没有父节点,直接单独维护即可,时间复杂度 \(O(n\log a_i)\)


代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=1234567; struct node{int y,next;}e[N];
int fat[N],as[N],et=1,n,Q,tot,rt[N],a[N],trie[N*20][2],c[N*20],ed[N*20],w[N*20],fa[N*20];
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f; 
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
void dfs(int x,int fa){
	fat[x]=fa;
	for (int i=as[x];i;i=e[i].next)
	    if (e[i].y!=fa) dfs(e[i].y,x);
}
void update(int rt,int x,int i,int opt){
	if (opt==-1){
		--c[ed[i]];
		for (int p=ed[i];fa[p];p=fa[p],--c[p])
			w[fa[p]]=(w[trie[fa[p]][0]]^w[trie[fa[p]][1]])<<1|(c[trie[fa[p]][1]]&1);
		ed[i]=0;
	}else{
		for (int j=0;j<20;++j){
		    int z=x&1; x>>=1;
		    if (!trie[rt][z]) trie[rt][z]=++tot;
		    fa[trie[rt][z]]=rt,rt=trie[rt][z];
	    }
		++c[ed[i]=rt];
		for (int p=ed[i];fa[p];p=fa[p],++c[p])
			w[fa[p]]=(w[trie[fa[p]][0]]^w[trie[fa[p]][1]])<<1|(c[trie[fa[p]][1]]&1);
	}
}
void plusone(int rt){
	swap(trie[rt][0],trie[rt][1]);
	if (trie[rt][0]) plusone(trie[rt][0]);
	w[rt]=(w[trie[rt][0]]^w[trie[rt][1]])<<1|(c[trie[rt][1]]&1);
}
int query(int x){
	int ans=0;
	for (int p=ed[x];fa[p];p=fa[p])
	if (trie[fa[p]][1]==p) ans=ans<<1|1;
	    else ans<<=1;
	return ans;
}
int main(){
	n=iut(),Q=iut();
	for (int i=1;i<n;++i){
		int x=iut(),y=iut();
		e[++et]=(node){y,as[x]},as[x]=et;
		e[++et]=(node){x,as[y]},as[y]=et;
	}
	dfs(1,0),tot=n;
	for (int i=1;i<=n;++i) rt[i]=i;
	for (int i=1;i<=n;++i){
		a[i]=iut();
		if (fat[i]) update(rt[fat[i]],a[i],i,1);
	}
	for (int i=1;i<=Q;++i)
	switch (iut()){
		case 1:{
			int x=iut();
			if (fat[x]==1) ++a[1];
			else if (fat[fat[x]]){
				int z=query(fat[x]);
				update(rt[fat[fat[x]]],z,fat[x],-1);
				update(rt[fat[fat[x]]],z+1,fat[x],1);
			}
			plusone(rt[x]);
			break;
		}
		case 2:{
			int x=iut(),y=iut();
			if (x==1) a[x]-=y;
			else{
				int z=query(x);
				update(rt[fat[x]],z,x,-1);
				update(rt[fat[x]],z-y,x,1);
			}
			break;
		}
		case 3:{
			int x=iut(),z=w[rt[x]];
			if (fat[fat[x]]) z^=query(fat[x]);
			    else if (fat[x]==1) z^=a[1];
			print(z),putchar(10);
			break;
		}
	}
	return 0;
}

标签:rt,洛谷,fa,Trie,6018,int,trie,ans,节点
From: https://www.cnblogs.com/Spare-No-Effort/p/18184922

相关文章

  • 洛谷题单指南-动态规划3-P1775 石子合并(弱化版)
    原题链接:https://www.luogu.com.cn/problem/P1775题意解读:计算合并石子的最小代价,区间DP。解题思路:状态表示:dp[i][j]表示将第i~j堆石子合并的最小代价,m[i]表示第i堆石子质量,s[i]表示前i堆石子质量前缀和状态转移:考虑最后一次合并,设最后一次合并是将i~k合成的一堆与k+1~j合成......
  • 洛谷题单指南-动态规划2-P3147 [USACO16OPEN] 262144 P
    原题链接:https://www.luogu.com.cn/problem/P3147题意解读:将一组数据两两相邻且相同的合并,合并成一个数值+1的数,求合并后的最大值。解题思路:考虑合并后的最大数i,其最后一次必然是由两个i-1合并而来的设dp[i][j]表示以j为左端点,合并最大值为i时的右端点的下一个位置如图:dp[i......
  • ERROR: CUDA out of memory. Tried to allocate 254.00 MiB.
    正在将samples/llm/大模型技术栈-算法与原理.md添加到向量库,共包含30条文档Batches:0%||0/1[00:00<?,?it/s]2024-05-1010:21:36,963-embeddings_api.py[li......
  • 5.9洛谷收获
    今天发现了一个有用的容器,那就是向量,用bool类型的向量简直不要太方便,尤其是对于二极管问题,比如B2094然后用向量模拟栈也比较方便点击查看代码#include<iostream>#include<vector>usingnamespacestd;classStack{private:vector<int>elements;public://......
  • 洛谷 P1031 [NOIP2002 提高组] 均分纸牌 题解
    题目简述有$N$堆纸牌,编号分别为$1,2,\ldots,N$。每堆上有若干张,但纸牌总数必为$N$的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为$1$堆上取的纸牌,只能移到编号为$2$的堆上;在编号为$N$的堆上取的纸牌,只能移到编号为$N-1$的堆上;其他堆上取的纸牌,可......
  • 洛谷 P1012 [NOIP1998 提高组] 拼数 题解
    题目简述设有$n$个正整数$a_1\dotsa_n$,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。题目分析定义设$X$为数字$x$的字符串形式。$A+B$表示字符串$A$和字符串$B$相连组成的字符串。思路既然要构造最优解,显然如果有不优的情况的话,就需要对序列进行......
  • #dp,Dilworth定理#洛谷 4934 礼物
    题目传送门分析首先,可以放在一起当且仅当\(\max\{a_i,a_j\}\&\min\{a_i,a_j\}\neq\min\{a_i,a_j\}\)根据Dilworth定理可知最小链划分中链的数目等于最长反链的长度所以设\(dp[i]\)表示以\(i\)为结尾的反链的最大长度,则\(dp[i]=\max_{j|i}\{dp[j]\}+[a_k==i]\)......
  • 洛谷题单指南-动态规划2-P4310 绝世好题
    原题链接:https://www.luogu.com.cn/problem/P4310题意解读:求最长的子序列长度,使得每相邻两个元素&操作不为0。解题思路:直观来看,可以通过类似最长上升子序列的算法,进行状态转移,但是复杂度为O(n^2),会超时状态表示:dp[i]表示前i个数能产生满足条件的子序列的最长长度状态转移:dp......
  • 洛谷题单指南-动态规划2-P1833 樱花
    原题链接:https://www.luogu.com.cn/problem/P1833题意解读:在有限的时间内,看n株樱花树,第i株樱花树可以看pi次,看每株樱花树耗费时间ti,看每株樱花树一次美学值ci,求最多能看到多少美学值。解题思路:本题实质是一个混合背包问题(pi>0是多重背包,pi=0是完全背包):背包容量:总时间,可以根据......
  • 历史研究(洛谷AT_joisc2014_c 歴史の研究)
    历史研究(洛谷AT_joisc2014_c 歴史の研究)题目描述IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。日记中记录了连续N天发生的事件,大约每天发生一件。......