树——仓鼠找 sugar
仓鼠找 sugar
题目来源：https://www.luogu.com.cn/problem/P3398
题目描述
小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 1 ∼ n 1sim n 1∼n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（ a a a）到餐厅（ b b b），而他的基友同时要从他的卧室（ c c c）到图书馆（ d d d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？
小仓鼠那么弱，还要天天被 zzq 大爷虐，请你快来救救他吧！
输入格式
第一行两个正整数 n n n 和 q q q，表示这棵树节点的个数和询问的个数。
接下来 n − 1 n-1 n−1 行，每行两个正整数 u u u 和 v v v，表示节点 u u u 到节点 v v v 之间有一条边。
接下来 q q q 行，每行四个正整数 a a a、 b b b、 c c c 和 d d d，表示节点编号，也就是一次询问，其意义如上。
输出格式
对于每个询问，如果有公共点，输出大写字母 Y；否则输出N。
样例 #1
样例输入 #15 5 2 5 4 2 1 3 1 4 5 1 5 1 2 2 1 4 4 1 3 4 3 1 1 5 3 5 1 4 12345678910 样例输出 #1
Y N Y Y Y 12345
提示
本题时限 1s，内存限制 128M，因新评测机速度较为接近 NOIP 评测机速度，请注意常数问题带来的影响。
20 % 20% 20% 的数据 n , q ≤ 200 n, qle200 n,q≤200。
40 % 40% 40% 的数据 n , q ≤ 2 × 1 0 3 n, qle 2times10^3 n,q≤2×103。
70 % 70% 70% 的数据 n , q ≤ 5 × 1 0 4 n, qle 5times10^4 n,q≤5×104。
100 % 100% 100% 的数据 1 ≤ n , q ≤ 1 0 5 1le n, qle10^5 1≤n,q≤105。
总结
最近公共祖先
最近公共最先又称lca，它可以解决以下问题：
在树中可以更快的找到公共祖先，可以通过两种方式实现:
| 1. 通过检测二者的depth来判断是否要往上跳，采用二进制的形式进行扩增法来跳，这种方法需要用bfs来初始化depth数组
| 2 .采用targin算法，这种算法是通过dfs的方式先将树标记成3种状态，第一种是未遍历，第二种是正在遍历，第三种是已遍历并回溯
次小生成树，通过kurscal算法（与上述的bfs算法写法类似），就是要用结构体（kurscal算法都是这样写的）来存储，关键是有判断是不是树节点，因为最后要使sum+w-wi最小，sum是权值。所以lca可以快速计算出a，b之间的最大边权与次大边权。
总之lca可以利用倍增的方式快速的计算出某个节点与公共祖先之间的距离，比如da+db-2dp
lca可以用来算树中节点距离
两条路求是否能碰面，就像这道题，我们得知道一个结论，询问树上
a到b，c到d的两条路径是否相交我们容易发现，如果相交，记x=lca(a,b)y=lca(c,d)，则必有x在c~ d路径上或y在a~ b路径上，——引用来源
注意，LCA这样的题一般题目都有都以最短路算……然后求什么什么碰面或者某个人走到某个地方是否喜欢某个东西
代码
//感觉有点lca，但一般的lca题目只要求两点的最近公共祖先，但这道题有个结论 //如果a=lca(x,y),b=lca(z,k)，如果dist(a,x)+dist(x,b)==dist[a,b] #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 1e5+10,M = 2*N; int f[N][17]; int n,m; int depth[N]; int e[M],ne[M],h[N],idx; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs(int u){ memset(depth,0x3f,sizeof depth); queue<int>q; depth[0]=0; depth[u]=1; q.push(u); while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(depth[j]>depth[t]+1){ depth[j]=depth[t]+1; q.push(j); f[j][0]=t; for(int k=1;k<=16;k++){ f[j][k]=f[f[j][k-1]][k-1]; } } } } } int lca(int x,int y){ if(depth[x]<depth[y])swap(x,y); for(int k=16;k>=0;k--){ if(depth[f[x][k]]>=depth[y]){ x=f[x][k]; } } if(x==y)return x; for(int k=16;k>=0;k--){ if(f[x][k]!=f[y][k]){ x=f[x][k]; y=f[y][k]; } } return f[x][0]; } int dist(int a,int b){ int c=lca(a,b); return abs(depth[c]-depth[a])+abs(depth[c]-depth[b]); } int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; add(a,b),add(b,a); } bfs(1); while(m--){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; int x=lca(x1,y1),y=lca(x2,y2); if(dist(x1,y)+dist(y1,y)==dist(x1,y1)||dist(x2,x)+dist(y2,x)==dist(x2,y2)){ puts("Y"); }else{ puts("N"); } } return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105细节：不要在那个for循环的时候把k>=0写成k了
LCA模板
#include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 5e5+10,M = 2*N; int e[M],ne[M],h[N],idx; int f[N][17];//f[i][j] 从i开始向上走2^j步所能走到的节点 int n,m,root; int depth[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs(int root){ memset(depth,0x3f,sizeof depth); depth[0]=0; depth[root]=1; queue<int> q; q.push(root); while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(depth[j]>depth[t]+1){ depth[j]=depth[t]+1; q.push(j); f[j][0]=t;//j跳0步就到了t for(int k=1;k<=15;k++){ f[j][k]=f[f[j][k-1]][k-1];//倍增的思想 } } } } } int lca(int x,int y){ if(depth[x]<depth[y])swap(x,y); for(int k=15;k>=0;k--){ if(depth[f[x][k]]>=depth[y]){ //x深度比y深 x=f[x][k]; } } if(x==y)return x; for(int k=15;k>=0;k--){ if(f[x][k]!=f[y][k]){ x=f[x][k]; y=f[y][k]; } } return f[x][0]; } int main(){ cin>>n>>m>>root; memset(h,-1,sizeof h); for(int i=1;i<=n-1;i++){ int a,b; cin>>a>>b; add(a,b),add(b,a); } bfs(root); while(m--){ int x,y; cin>>x>>y; int p=lca(x,y); cout<<p<<endl; } return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990相关知识
北美高端宠物食品Sugar Fox狗粮 参加第6届北京国际宠物用品展
宠物：Sugar Gliders是好宠物吗？
仓鼠丢了怎么找
【宠物树】
仓鼠宠物医生怎么找
科普一下这种网红宠物，别再误以为是仓鼠或蝙蝠了...
仓鼠从笼子里跑出来在家里怎么找
仓鼠食物大全
金渐层找领养
仓鼠食物大全.doc
网址: 树——仓鼠找 sugar https://m.mcbbbk.com/newsview515152.html
| 上一篇: 养鼠日常分享 萌宠小仓鼠 关于仓 |
下一篇: 特斯拉的“狗模式”和“哨兵模式” |
