首页 > 其他分享 >Living-Dream 系列笔记 第67期

Living-Dream 系列笔记 第67期

时间：2024-07-29 12:07:25浏览次数：19  
标签：Living int LCA dep 67 -- Dream dp dis

树上倍增：维护 \(dp_{i,j}\) 表示节点 \(i\) 向上移动 \(2^j\) 步所到达的节点编号、区间最值、区间和等信息。

倍增求 LCA：

  • 预处理：

    • 令 \(dp_{i,j}\) 表示 \(i\) 向上走 \(2^j\) 步所到达的节点。

    • 转移：\(dp_{i,j}=dp_{dp_{i,j-1},j-1}\)。

    • 初始：\(dp_{i,0}=fa_i\)。

  • 查询：

    • 约定 \(x\) 深度更大。

    • \(x\) 倍增向上跳直到与 \(y\) 同深度。

    • 特判 \(x,y\) 是否重叠。

    • \(x,y\) 一起向上跳，但不重叠（若重叠了还跳就不是 LCA 了）。

    • 跳完后 \(fa_x\) 即为 LCA。

  • 性质：

    • LCA 与根有关。

    • 树上两点距离与 LCA 无关。

    • 设 \(dis_x\) 表示树上节点 \(x\) 到根的距离，

      \(LCA(x,y)\) 表示树上两点 \(x,y\) 的 LCA，

      则树上两点 \(x,y\) 距离为 \(dis_x+dis_y-dis_{LCA(x,y)}\)。

P3379

板子。

code 
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5,M=31;
int n,m,s;
vector<int> G[N<<1];
int dep[N],dp[N][M];

void initLCA(int cur,int fa){
	dep[cur]=dep[fa]+1;
	dp[cur][0]=fa;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int i:G[cur])
		if(i!=fa)
			initLCA(i,cur);
}
int queryLCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>s;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	initLCA(s,0);
	while(m--){
		int x,y; 
		cin>>x>>y,cout<<queryLCA(x,y)<<'\n';
	}
	return 0;
}

P3398

因为树上节点不会有多个父节点，因此要么 \(LCA(a,b)\) 落在路径 \(c \to d\) 上，要么 \(LCA(c,d)\) 落在路径 \(a \to b\) 上。

检查一个点是否落在一条路径上，就检查该点到路径两端点的距离之和是否为路径长即可。

code 
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5,M=31;
int n,q;
vector<int> G[N<<1];
int dep[N],dp[N][M];

void initLCA(int cur,int fa){
	dep[cur]=dep[fa]+1;
	dp[cur][0]=fa;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int i:G[cur])
		if(i!=fa)
			initLCA(i,cur);
}
int queryLCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	initLCA(1,0);
	while(q--){
		int a,b,c,d; cin>>a>>b>>c>>d;
		int LCAab=queryLCA(a,b);
		int LCAcd=queryLCA(c,d);
		int LCAlc=queryLCA(LCAab,c);
		int LCAld=queryLCA(LCAab,d);
		int LCAla=queryLCA(LCAcd,a);
		int LCAlb=queryLCA(LCAcd,b);
		int DISab=dep[a]+dep[b]-2*dep[LCAab];
		int DIScd=dep[c]+dep[d]-2*dep[LCAcd];
		int DISlc=dep[LCAab]+dep[c]-2*dep[LCAlc];
		int DISld=dep[LCAab]+dep[d]-2*dep[LCAld];
		int DISla=dep[LCAcd]+dep[a]-2*dep[LCAla];
		int DISlb=dep[LCAcd]+dep[b]-2*dep[LCAlb];
		cout<<(DISlc+DISld==DIScd||DISla+DISlb==DISab?"Y\n":"N\n");
	} 
}

P4281

很容易发现一个性质：三个点两两的 LCA 必然只有两种可能（即必然会重合一个）。

简单画个图便可知，那个不一样的 LCA 一定是集合点。

继续看图分析，可得三个点 \(x,y,z\) 到集合点的距离即为：

\[dis_x+dis_y+dis_z-dis_{LCA(x,y)}-dis_{LCA(x,z)}-dis_{LCA(y,z)} \]

code 
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5,M=31;
int n,m;
vector<int> G[N<<1];
int dep[N],dp[N][M];

void initLCA(int cur,int fa){
	dep[cur]=dep[fa]+1;
	dp[cur][0]=fa;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int i:G[cur])
		if(i!=fa)
			initLCA(i,cur);
}
int queryLCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	initLCA(1,0);
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		int LCAxy=queryLCA(x,y);
		int LCAxz=queryLCA(x,z);
		int LCAyz=queryLCA(y,z);
		int ans=0;
		if(LCAxy==LCAxz) ans=LCAyz;
		else if(LCAxy==LCAyz) ans=LCAxz;
		else ans=LCAxy;
		cout<<ans<<' '<<dep[x]+dep[y]+dep[z]-dep[LCAxy]-dep[LCAxz]-dep[LCAyz]<<'\n';
	}
	return 0;
}

CF379F

首先新直径一定得经过新加边（不会更劣），并且新加的两个点是等价的。

于是我们随便选个新加点 \(u\)，令原直径端点为 \(x,y\)，若 \(dis_{u,x}>dis_{x,y}\) 或 \(dis_{u,y}>dis_{x,y}\)，则 \(u\) 可替代 \(x\) 或 \(y\)。

求距离时每次新加两个点就单独维护一下 LCA 即可。\(O(q \log n)\)。

code 
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5,M=31;
int m,n=4;
int dep[N<<1],dp[N<<1][M];
vector<int> G[N<<1];

void preLCA(int cur,int fa){
    dp[cur][0]=fa;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
}
int queryLCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
    if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}

int main(){
	ios::sync_with_stdio(0);
	dep[1]=1;
	for(int i=2;i<=4;i++){
		G[1].push_back(i);
		dep[i]=2;
        preLCA(i,1);
	}
	cin>>m;
	int x=2,y=3,ans=2;
	while(m--){
		int u; cin>>u;
		for(int i=1;i<=2;i++){
			n++;
			G[u].push_back(n);
            G[n].push_back(u);
			dep[n]=dep[u]+1;
            preLCA(n,u);
		}
		int LCAnx=queryLCA(n,x);
		int LCAny=queryLCA(n,y);
		int DISnx=dep[n]+dep[x]-2*dep[LCAnx];
		int DISny=dep[n]+dep[y]-2*dep[LCAny];
        if(DISnx<=ans&&DISny<=ans) 
            cout<<ans<<'\n';
		else if(DISnx>ans){
			cout<<DISnx<<'\n'; 
			ans=DISnx,y=n;
		}
		else{
			cout<<DISny<<'\n';
			ans=DISny,x=n;
		}
	}
	return 0;
}

P8972

首先必须将边权都转为整数。

然后我们发现若干个小数相乘能为整数，则必须满足它们分解质因数后 \(2\) 或 \(5\) 中最少的个数必须 \(\ge\) 小数位数之和，这样才能抵消掉所有小数位数。

于是我们在 LCA 中维护 \(cnt2_x,cnt5_x,dis_x\) 分别表示节点 \(x\) 到根节点的 边权的质因子中 \(2\) 的个数、\(5\) 的个数，以及小数位数和，然后依上述条件判断即可。

code 
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=5e5+5,M=31;
const int INF=1e16;
int n,q,a[N];
int cnt2[N],cnt5[N];
struct E{ int v,w,dot; };
vector<E> G[N<<1];
int dep[N],dp[N][M],dis[N];

int cntdiv(int x,int y){
	if(!x) return INF;
	int res=0;
	while(x&&x%y==0)
		x/=y,res++;
	return res;
}
void initLCA(int cur,int fa){
	dep[cur]=dep[fa]+1;
	dp[cur][0]=fa;
	for(int i=1;(1<<i)<=dep[cur];i++)
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(auto i:G[cur]){
		if(i.v!=fa){
			dis[i.v]=dis[cur]+i.dot;
			cnt2[i.v]=cnt2[cur]+cntdiv(i.w,2);
			cnt5[i.v]=cnt5[cur]+cntdiv(i.w,5);
			initLCA(i.v,cur);
		}
	}
}
int queryLCA(int x,int y){
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[dp[x][i]]>=dep[y])
			x=dp[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(dp[x][i]!=dp[y][i])
			x=dp[x][i],y=dp[y][i];
	return dp[x][0];
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v; double w;
		cin>>u>>v>>w;
		int dot=0;
		while(w!=floor(w)) 
			w*=10.0,dot++;
		G[u].push_back({v,floor(w),dot}),
		G[v].push_back({u,floor(w),dot});
	}
	initLCA(1,0);
	while(q--){
		int x,y; 
		cin>>x>>y;
		int LCAxy=queryLCA(x,y);
		int DISxy=dis[x]+dis[y]-2*dis[LCAxy];
		int two=cnt2[x]+cnt2[y]-2*cnt2[LCAxy]+cntdiv(a[x],2);
		int five=cnt5[x]+cnt5[y]-2*cnt5[LCAxy]+cntdiv(a[x],5);
		cout<<(min(two,five)>=DISxy?"Yes\n":"No\n");
	}
	return 0;
}

标签：Living,int,LCA,dep,67,--,Dream,dp,dis
From： https://www.cnblogs.com/XOF-0-0/p/18329814

相关文章

  • 2024世界人工智能大会：智象未来（HiDream.ai）入围多行业示范性应用案例
    在刚刚闭幕的世界人工智能大会（2024WAIC）上，智象未来（HiDream.ai）依托自身领先的行业技术，入围多行业示范性应用案例，充分展示了其在人工智能领域的卓越成就和创新能力。会上，智象未来（HiDream.ai）联合创始人兼CTO姚霆博士正式推出了备受期待的“智象大模型2.0”。新一代多模态大模型......
  • 洛谷P1067 [NOIP2009 普及组] 多项式输出
    题目链接：-P1067[NOIP2009普及组]多项式输出题目叙述：[NOIP2009普及组]多项式输出题目描述一元n次多项式可用如下的表达式表示：多项式中自变量为x，从左到右按照次数递减顺序给出多项式。多项式中只包含系数不为0的项。如果多项式n次项系数为正，则多项式开头......
  • 华为S6700交换机的命名规则
      表6 S6700交换机的命名规则（适用于S6730/S6735/S6755款型）标号含义A设备类型（1位）固定为S，表示设备为交换机。B网络定位（1位）6：汇聚交换机5：高端接入交换机3：中端接入交换机C市场定位（1位）7：企业网产品系列D交换机子系列（2位）十位表示更新......
  • [题解]P2672 [NOIP2015 普及组] 推销员
    P2672[NOIP2015普及组]推销员为了便于操作，将住户信息按疲劳值从大到小排序。那么对于选\(X\)个住户，有\(2\)种情况：选疲劳值前\(X\)大的住户，答案即为\(\sum\limits_{i=1}^Xa[i]+2\times\max\limits_{i=1}^Xs[i]\)。选疲劳值前\(X-1\)大的住户，然后在剩下的住户中，距离比......
  • 267java jsp SSM防疫信息登记系统风险地区管理（源码+文档+PPT+运行视频+讲解视频）
     项目技术：SSM+Maven+Vue等等组成，B/S模式+Maven管理等等。环境需要1.运行环境：最好是javajdk1.8，我们在这个平台上运行的。其他版本理论上也可以。2.IDE环境：IDEA，Eclipse,Myeclipse都可以。推荐IDEA;3.tomcat环境：Tomcat7.x,8.x,9.x版本均可4.硬件环境：windows7/8/1......
  • LeetCode767 重构字符串
    题解通常直接思考最佳策略是十分困难的，我们不妨思考每一种情况需要如何处理：整个字符串只有一种字符若字符串长度为\(1\)，那么字符串本身即为答案；若字符串长度大于等于\(2\)，那么不存在可行方案整个字符串只有两种字符\(c_1，c_2\)，数量分别为\(n_1，n_2\)若字符\(c_1\)的......
  • Living-Dream 系列笔记 第66期
    RMQ问题/ST表：静态区间求最值。实现（以最大值为例）：倍增dp,预处理\(st_{i,j}\)表示区间\([i,i+2^j-1]\)内的最大值，我们有转移方程：\[st_{i,j}=\max(st_{i,j-1},st_{i+2^{j-1},j-1})\]相当于是把\([i,i+2^{j-1}-1]\)与\([i+2^{j-1},i+2^j-1]\)这两段区间的最大值拼了......
  • steam休闲游戏推荐：《Mimpi Dreams》《Pizza Possum》《洞窟物语》
    对于想要放松娱乐的时刻，Steam平台上有一些非常受欢迎的休闲游戏，这里推荐三款：1、《Mimpi Dreams》《Mimpi Dreams》中文名为《米皮大冒险：梦境》，是一款由 Silicon Jelly 开发的冒险解谜游戏。该游戏的故事承接前作，小狗米皮在成功找到主人并一同回家后，某天夜晚受到梦魇的......
  • 洛谷题单指南-前缀和差分与离散化-P2367 语文成绩
    原题链接：https://www.luogu.com.cn/problem/P2367题意解读：对于数组s[]，给指定q个区间[x,y]里每个数增加z，计算操作之后最小的数。解题思路：1、暴力做法对于每一个区间[x,y]，枚举给每一个数增加z，然后遍历查找最小值，总体时间复杂度为O(N^2)，不可行。2、一维差分对于给指定区间[x,......
  • CF567E 题解
    题面考虑如何一条边是必经之路：设\(cntl_i\)为从\(s\)到\(i\)走最短路的方案数，\(cntr_i\)为从\(i\)到\(t\)最短路方案数。由乘法原理，如果对于边\(e_i=(u,v)\)，\(cnt_t=cnt_u\timescntr_v\)，则\(e_i\)是最短路上的必经边，输出Yes即可。如果\(cnt_u\timescntr_v=0......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99