首页 > 其他分享 >G. wxhtzdy ORO Tree

G. wxhtzdy ORO Tree

时间:2023-09-28 21:01:29浏览次数:40  
标签:fa int wxhtzdy Tree st ORO num ans --

G. wxhtzdy ORO Tree

前提知识:lca求最近公共祖先(倍增)
因为或运算越多值就越大,好像跟上一个相反,所以满足单调不降
要点1:利用数组来对每个点到其祖先节点的或和进行计算(倍增)
要点2:分别对左右两边进行分析到lca点,这样确保无误
要点3:因为满足单调不降,所以遇到大于的节点对左边才有意义
最后,提一点思路:右边v->w(lca),w->z;左边u->z(意义同上);

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int a[N];
vector<int> g[N];
int d[N],fa[N][22], st[N][22];
void dfs(int u, int father) {
	d[u] = d[father] + 1; fa[u][0] = father;
	st[u][0] = a[father];//st从u点到根节点的或和(不包括u点)
	for (int i = 1; i <= 19; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		st[u][i] = st[fa[u][i - 1]][i - 1] | st[u][i - 1];//注意st里是fa[u][i-1],而不是st[u][i-1],因为st是或值,不是节点了
	}
	for (int v:g[u]) {
		if (v == father) continue;
		dfs(v, u);
	}
};
int lca(int u, int v) {//寻找最近公共祖先
	if (d[u] < d[v]) swap(u, v);
	for (int i = 19; i>=0; i--) {
		if (d[fa[u][i]] >= d[v]) u = fa[u][i];//注意d里面的内容,不要误写成u了
	}
	if (u == v) return u;
	for (int i = 19; i >= 0; i--) {
		if (fa[u][i]!= fa[v][i])
			u = fa[u][i], v = fa[v][i];//注意,当时把v写成u死活过不了
	}
	return fa[u][0];
}
int find(int u,int v){//u到v点的或和,只要保证v为最浅的就不用swap了
	int ans=a[u];
	for(int i=19;i>=0;i--){
		if(d[fa[u][i]]>=d[v])
		ans|=st[u][i],u=fa[u][i];
	}
	return ans;
}
int qry(int u, int v) {
	int w = lca(u, v), num = a[u], cnt = __builtin_popcount(num);//库函数,计算数字二进制位1的个数
	int x=find(v,w),ans=0;//获得另一边到最近公共祖先的值
	while(d[u]>=d[w]){//到达最近公共祖先就退出,表示左边或者右边已经完毕
		ans=max(ans,cnt+__builtin_popcount(x|find(u,w)));//求最大,右边点到左边某点的或和
		for(int i=19;i>=0;i--)
			if(__builtin_popcount(num|st[u][i])==cnt)//相等说明左边的没有变化,没变化往前走(但可导致右边的或和发生变化,所以只要两边都分别进行计算,就不会有遗漏了)
				num|=st[u][i],u=fa[u][i];
		num|=st[u][0],u=fa[u][0];//更新左节点的位置
		cnt=__builtin_popcount(num);//计算左边当前的或和
	}
	return ans;
}
void solve() {
	int n;
	cin>>n;
	for (int i = 1; i <= n; i++)  cin>>a[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);//lca倍增
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << max(qry(u, v), qry(v, u))<<' ';//输出两者的最大值(从右往左,或者从左往右)
	}
	cout << '\n';
	for(int i=1;i<=n;i++) g[i].clear();//及时清除

}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

标签:fa,int,wxhtzdy,Tree,st,ORO,num,ans,--
From: https://www.cnblogs.com/bu-fan/p/17736476.html

相关文章

  • qoj6735. Tree (The 1st Universal Cup. Stage 22: Shaanxi)
    https://qoj.ac/contest/1287/problem/6735考虑定一个根,然后把每个点的点权附属在父边权上,让每条边的边权变成一个pair。这样,一个符合条件的路径需要满足的条件是:路径内所有边的边权pair相同,以及路径根节点(lca)的颜色符合。对于当前树上每个边权相同的连通块分开考虑。对......
  • 根据一个数组,创建一个Segment Tree(线段树)
    线段树的特点线段树的优势线段树的构造过程(0,5)37:数组元素下标0~5的元素之和是37(0,2)21:数组元素下标0~2的元素之和是21线段树的基本数据结构(结点结构由五个分量组成)运行结果(C语言代码)递归的创建一颗线段树,然后中序、先序、后序遍历这个结点#include<stdio.h>#include<st......
  • Go - ERROR: fatal error: all goroutines are asleep - deadlock!
    main.go:packagemainimport"fmt"funcmain(){ch:=make(chanint)ch<-1a:=<-chfmt.Println(a)}Goterror:zzh@ZZHPC:/zdata/MyPrograms/Go/testing$gorunmain.gofatalerror:allgoroutinesareasleep-deadlo......
  • 【UVA 536】Tree Recovery 题解(根据遍历序列还原二叉树)
    小瓦伦丁非常喜欢玩二叉树。她最喜欢的游戏是随机构建查找节点中带有大写字母的二叉树。这是她创作的一个例子:为了给后代记录她的树,她为每棵树写下了两个字符串:预订单遍历(根、左子树、右子树)和有序遍历(左子树、根、右子树。对于上面绘制的树,预序遍历是DBACEGF,有序遍历是ABCDEFG......
  • goland编辑器编译的时候报错package xxx is not in GOROOT的原因排查
    先介绍下,我的目录部署情况1、GOROOT=C:\ProgramFiles\Go(我的golang环境装在c盘的)2、GOPATH=E:\Go(项目目录我放在E盘的)3、GO111MODULE=auto(默认值,没有改过)4、GOVERSION=go1.20.6(我的golang版本)5、项目结构,遵循官方推荐的方式E:\Go——bin——pkg——src 6、本次需要......
  • Merkle Tree 简介
    Merkle树(MerkleTree)是一种树状数据结构,通常用于验证大规模数据集的完整性和一致性。它的名字来源于其发明者RalphMerkle。Merkle树在密码学、分布式系统和区块链等领域得到广泛应用,尤其在区块链中,它用于验证交易和区块的完整性,确保数据不被篡改。下面是Merkle树的介绍:1.......
  • 逻辑树(LogicTree)和可视化树(VisualTree)
    遍历逻辑树和可视化树FrameworkElementLevel.(FrameworkElementType).(FrameworkElementName)[DataContextType]publicstaticclassTreeHelper{publicstaticstringgetTree(FrameworkElementcontainer){StringBuildersb=newStringBuilder();......
  • 在线直播系统源码,取CTreeCtrl控件选中节点的文字
    在线直播系统源码,取CTreeCtrl控件选中节点的文字 voidCAboutDlg::OnSelchangedTree1(NMHDR*pNMHDR,LRESULT*pResult) {NM_TREEVIEW*pNMTreeView=(NM_TREEVIEW*)pNMHDR;//TODO:Addyourcontrolnotificationhandlercodehere    MessageBox(m_tree1.GetIte......
  • abc321E - Complete Binary Tree
    E-CompleteBinaryTree首先我们只考虑x子树中的答案,非常明显,一定是一个连续的区间,那么我们只需要找到两个端点即可,左端点一直往左走即可,但是右端点要注意,如果走不了,如果左端点存在,说明n就是我们的右端点。处理完子树之后往上跳即可,因为树高只有60#include<cstdio>#include<......
  • 使用Vue3+elementPlus的Tree组件实现一个拖拽文件夹管理
    目录1、前言2、分析3、实现4、踩坑4.1、拖拽辅助线的坑4.2、数据的坑4.3、限制拖拽4.4、样式调整1、前言最近在做一个文件夹管理的功能,要实现一个树状的文件夹面板。里面包含两种元素,文件夹以及文件。交互要求如下:创建、删除,重命名文件夹和文件可以拖拽,拖拽文件到文件夹中,或......