首页 > 其他分享 >CF950Div3 G. Yasya and the Mysterious Tree(01Trie)

CF950Div3 G. Yasya and the Mysterious Tree(01Trie)

时间:2024-07-01 21:32:21浏览次数:17  
标签:ch val 01Trie int Tree tp Mysterious now Yasya

Problem

题目地址

Solution

设 \(s[u]\) 是根到 \(u\) 路径上的异或和,树上任意两点 \(u,v\) 的路径异或和可表示为 \(s[u] \oplus s[v]\)。

考虑查询操作 ? v x 即求 \(\max\{ s[v] \oplus s[u] \oplus x |\ \ 1 \le u \le n, u \not = v\}\) ,若把 \(s[v] \oplus x\) 看作一个整体,这恰好是 01Trie 可以解决的问题。

考虑修改操作 ^ y 对查询的影响:由于是全局 \(\oplus y\),当路径长度为偶数时对结果没有影响,路径长度为奇数时则会有影响。于是我们可以开两个 01Tire,将树黑白染色,同一颜色的 \(s[u]\) 存入相同的 01Trie。同色点间的路径长度一定为偶数,反之不同颜色点间的路径长度一定为奇数。

注意到查询时,01Tire对应的集合里面不应该有自己,所以要涉及到 01Trie的删除操作。

时间复杂度 \(O(n*30)\)

Code

Talk is cheap.Show me the code

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
typedef pair<int,int> pii;
const int N = 2e5+7;
const int MAXN = 6e6+7;
int n,m;
int val[N];
bool tp[N];
vector<pii> E[N];
struct Trie {
	int tot;
	int cnt[MAXN];
	int ch[MAXN][2];
	void Init() {
		for(int i=0;i<=tot;++i) {
			cnt[i] = ch[i][0] = ch[i][1] = 0;
		}
		tot = 0;
	}
	void insert(int x,int k) {
		int now = 0;
		for(int i=30;i>=0;--i) {
			int c = (x>>i)&1;
			if(!ch[now][c]) ch[now][c] = ++tot;
			now = ch[now][c];
			cnt[now] += k;
		}
	}
	int find_max(int x) {
		int now = 0, res = 0;
		for(int i=30;i>=0;--i) {
			int c = (x>>i)&1;
			if(ch[now][c^1] && cnt[ch[now][c^1]]) now = ch[now][c^1], res |= (1<<i);
			else {
				if(!(ch[now][c] && cnt[ch[now][c]])) return -1;
				now = ch[now][c];
			}
		}
		return res;
	}
}tree[2];
void Dfs(int u,int fa,int s) {
	tree[s].insert(val[u], 1);
	tp[u] = s;
	for(auto now : E[u]) {
		int v = now.first, w = now.second;
		if(v == fa) continue;
		val[v] = val[u] ^ w;
		Dfs(v, u, s^1);
	}
}
void solve() {
	n = read(), m = read();
	for(int i=1;i<n;++i) {
		int u = read(), v = read(), w = read();
		E[u].push_back(mp(v, w));
		E[v].push_back(mp(u, w));
	}
	Dfs(1, 0, 0);
	int y = 0;
	while(m--) {
		char op;
		cin >> op;
		if(op == '^') {
			int x = read(); y ^= x;
		} else {
			int v = read(), x = read();
			tree[tp[v]].insert(val[v], -1);
			int mx1 = tree[tp[v]].find_max(val[v]^x);
			int mx2 = tree[tp[v]^1].find_max(val[v]^x^y);
			printf("%d\n",max(mx1, mx2));
			tree[tp[v]].insert(val[v], 1);
		}
	}
	
	for(int i=1;i<=n;++i) {
		E[i].clear();
		val[i] = tp[i] = 0;
	}
	tree[0].Init();
	tree[1].Init();
}
int main()
{
	int T = read();
	while(T--) {
		solve();
	}
	return 0;
}

Summary

01 Trie 可以解决的问题:

  • 某一个数与集合中的一个数的异或最大值。

标签:ch,val,01Trie,int,Tree,tp,Mysterious,now,Yasya
From: https://www.cnblogs.com/BaseAI/p/18278879

相关文章

  • Vue Ant Design中a-tree组件支持点击父节点名称(title\label)所有子节点选中
    核心代码<a-treeref="treeRef"class="draggable-tree"v-if="treeData.length":tree-data="treeData"......
  • sourcetree使用ssh拉取代码报错?看下是不是ssh客户端的问题以及相应的解决方案看这里~~
    相信很多软件开发的同学都很熟悉sourcetree,如果也有同学在使用过程中出现ssh拉取代码出现如下报错的问题这里比较头疼的是没法交互输入y确认缓存秘钥。Theserver'shostkeyisnotcachedintheregistry.Youhavenoguaranteethattheserveristhecomputeryouthi......
  • Leetcode 3203. Find Minimum Diameter After Merging Two Trees
    Leetcode3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路2.代码实现题目链接:3203.FindMinimumDiameterAfterMergingTwoTrees1.解题思路这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历,不断地删除已访问的叶子节点,并加入......
  • [题解]CF1714F Build a Tree and That Is It
    思路由于题目中说这是一棵无根树,不太方便思考,于是,我们可以假装把这棵树看做有根树。首先我们令\(d_1,d_2,d_3\)分别表示从根节点到节点\(1,2,3\)的长度(不算相交部分)。那么我们可以得到下式:\[\left\{\begin{matrix}d_{12}=d_1+d_2\\d_{13}=d_1+d_3\\......
  • [题解]CF1741D Masha and a Beautiful Tree
    思路我们可以观察样例,不难发现:对于任意一段长度为\(2^k\)的区间中,如果最大值减最小值加\(1\)等于此区间的长度,那么一定有解。因为,我们的目标是使整个序列升序排列。因此,我们在一个区间内的最大值减最小值加\(1\)与区间长度是相等的。所以,我们可以用上述结论为判断无解的......
  • WPF TreeView 三层绑定模板
    在WPF应用程序中,使用TreeView来展示三层数据结构是一个常见的需求。为此,你需要定义适当的数据绑定和模板。以下是一个完整的示例代码,展示如何实现这一点。数据模型首先,我们需要定义三层数据模型。假设我们有三层数据结构:RootItem包含ChildItem,ChildItem又包含SubChildItem。pub......
  • CF1770E Koxia and Tree
    题目描述给定一棵\(n\)个点的树,在\(k\)个位置上存在蝴蝶,我们需要给\(n-1\)条边定向,如果一条边的起点有蝴蝶且终点没有蝴蝶,那么蝴蝶将被移动到终点,我们会按照给定边的顺序移动,问最终所有蝴蝶的树上距离的和的期望,答案除于\(\frac{k(k-1)}{2}\),对\(998244353\)取模\[k\len\le300......
  • ABC359 G - Sum of Tree Distance
    题目链接题目大意给出一棵树,树上每个节点都有一种颜色,求所有颜色相同的节点两两之间距离的总和。 题解想来写题解主要是看了一下官方解法都写的需要“重心分解”,应该是对应中文语境下的树的点分治。实际上点分治写起来很费事,可以用启发式合并替代。具体来说,dfs时每个节点......
  • abc359_G Sum of Tree Distance 题解
    题目链接:Atcoder或者洛谷先考虑暴力,显然是枚举整棵树的路径,这个枚举复杂度显示是\(O(n^2)\),还不考虑计算\(f(i,j)\),考虑使用点分治优化枚举复杂度:\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\),注意到\(f(i,j)\):当且仅当\(a[i]=a[j]\)时,答案加上\(dis(i,j......
  • Qt QTreeView 常见节点操作
    QTreeView作为项目最经常使用的空间,常用接口和操作必须熟悉熟悉在熟悉!!!1、节点遍历1voidParamSettingDlg::GetNode()2{3for(inti=0;i<model->rowCount();i++)4{5QStandardItem*item=model->item(i);67qDebug()<<"item......