信息型企业网站有哪些,wordpress文章摘要缩略图,永康网站定制,做安全宣传的是什么网站P3379
P3379 【模板】最近公共祖先#xff08;LCA#xff09; # 【模板】最近公共祖先#xff08;LCA#xff09;
## 题目描述
如题#xff0c;给定一棵有根多叉树#xff0c;请求出指定两个点直接最近的公共祖先。
## 输入格式
第一行包含三个正整数 $N,M,S$#… P3379
P3379 【模板】最近公共祖先LCA # 【模板】最近公共祖先LCA
## 题目描述
如题给定一棵有根多叉树请求出指定两个点直接最近的公共祖先。
## 输入格式
第一行包含三个正整数 $N,M,S$分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 $N-1$ 行每行包含两个正整数 $x, y$表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边数据保证可以构成树。
接下来 $M$ 行每行包含两个正整数 $a, b$表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。
## 输出格式
输出包含 $M$ 行每行包含一个正整数依次为每一个询问的结果。
## 样例 #1
### 样例输入 #1 5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
### 样例输出 #1 4 4 1 4 4
## 提示
对于 $30\%$ 的数据$N\leq 10$$M\leq 10$。
对于 $70\%$ 的数据$N\leq 10000$$M\leq 10000$。
对于 $100\%$ 的数据$1 \leq N,M\leq 500000$$1 \leq x, y,a ,b \leq N$**不保证** $a \neq b$。 样例说明
该树结构如下 
第一次询问$2, 4$ 的最近公共祖先故为 $4$。
第二次询问$3, 2$ 的最近公共祖先故为 $4$。
第三次询问$3, 5$ 的最近公共祖先故为 $1$。
第四次询问$1, 2$ 的最近公共祖先故为 $4$。
第五次询问$4, 5$ 的最近公共祖先故为 $4$。
故输出依次为 $4, 4, 1, 4, 4$。 2021/10/4 数据更新 fstqwq应要求加了两组数据卡掉了暴力跳。 #includebits/stdc.h
using namespace std;
const int N1e510,L19;
int n,m,s,f[N][20],head[N],k,dep[N],lo[N];
struct ed{int to,next;
}e[2*N];
void add(int x,int y){e[k].toy;e[k].nexthead[x];head[x]k;
}
void dfs(int x,int fa){f[x][0]fa;dep[x]dep[fa]1;for(int i1;i19;i)f[x][i]f[f[x][i-1]][i-1];for(int ihead[x];i!0;ie[i].next){int toe[i].to;if(to!fa)dfs(e[i].to,x);}
}
int lca(int x,int y){if(dep[x]dep[y])swap(x,y);while(dep[x]dep[y]){xf[x][lo[dep[x]-dep[y]]];//printf(oO%d,%d,%d\n,f[x][lo[dep[x]-dep[y]]],x,y);}if(xy) return x;for(int i19;i0;i--){if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}}return f[y][0];
}
int main(){//printf(%d,log(1));//memset(head,-1,sizeof(head));scanf(%d%d%d,n,m,s);for(int i2;iN;i){lo[i]lo[i/2]1;}for(int i1;in;i){int x,y;scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(s,0);//for(int i1;in;i)printf(%d ,dep[i]);while(m--){int x,y;scanf(%d%d,x,y);printf(%d\n,lca(x,y));}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 4
4 2
4 5
*/#includebits/stdc.h
using namespace std;
const int N5e510,L19;
int n,m,s,fa[N],head[N],k,dep[N],lo[N],ans[N];
bool vis[N];
vectorint e[N];
vectorpairint,int q[N];
int find(int x){if(fa[x]x)return x;return fa[x]find(fa[x]);
}
void dfs(int x){fa[x]x;vis[x]1;for(int i0;ie[x].size();i){int toe[x][i];if(!vis[to]){dfs(to);fa[to]x;}}for(int i0;iq[x].size();i){int cq[x][i].first,ccq[x][i].second;if(vis[c]){ans[cc]find(c);}}
}
int main(){//printf(%d,log(1));//memset(head,-1,sizeof(head));scanf(%d%d%d,n,m,s);for(int i1;in;i){int x,y;scanf(%d%d,x,y);e[x].push_back(y);e[y].push_back(x);}//for(int i1;in;i)printf(%d ,dep[i]);for(int i1;im;i){int x,y;scanf(%d%d,x,y);q[x].push_back((pairint,int){y,i});q[y].push_back((pairint,int){x,i});}vis[0]1;dfs(s);for(int i1;im;i){printf(%d\n,ans[i]);}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 3
2 2
4 5
*/
文章转载自： http://www.morning.rkfh.cn.gov.cn.rkfh.cn http://www.morning.kkrnm.cn.gov.cn.kkrnm.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.jsphr.cn.gov.cn.jsphr.cn http://www.morning.qlsbz.cn.gov.cn.qlsbz.cn http://www.morning.mbhdl.cn.gov.cn.mbhdl.cn http://www.morning.huarma.com.gov.cn.huarma.com http://www.morning.gtqws.cn.gov.cn.gtqws.cn http://www.morning.rzbcz.cn.gov.cn.rzbcz.cn http://www.morning.kzpxc.cn.gov.cn.kzpxc.cn http://www.morning.yzktr.cn.gov.cn.yzktr.cn http://www.morning.rfpb.cn.gov.cn.rfpb.cn http://www.morning.kwxr.cn.gov.cn.kwxr.cn http://www.morning.qyqmj.cn.gov.cn.qyqmj.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.rjnx.cn.gov.cn.rjnx.cn http://www.morning.xzjsb.cn.gov.cn.xzjsb.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.sgmis.com.gov.cn.sgmis.com http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.fprll.cn.gov.cn.fprll.cn http://www.morning.rtpw.cn.gov.cn.rtpw.cn http://www.morning.ygpdm.cn.gov.cn.ygpdm.cn http://www.morning.chehb.com.gov.cn.chehb.com http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.qnbgh.cn.gov.cn.qnbgh.cn http://www.morning.djlxz.cn.gov.cn.djlxz.cn http://www.morning.fnjrh.cn.gov.cn.fnjrh.cn http://www.morning.dnqliv.cn.gov.cn.dnqliv.cn http://www.morning.ey3h2d.cn.gov.cn.ey3h2d.cn http://www.morning.lgsfb.cn.gov.cn.lgsfb.cn http://www.morning.srbl.cn.gov.cn.srbl.cn http://www.morning.frzdt.cn.gov.cn.frzdt.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.ailvturv.com.gov.cn.ailvturv.com http://www.morning.wmlby.cn.gov.cn.wmlby.cn http://www.morning.yrck.cn.gov.cn.yrck.cn http://www.morning.ydnx.cn.gov.cn.ydnx.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.rtspr.cn.gov.cn.rtspr.cn http://www.morning.bpds.cn.gov.cn.bpds.cn http://www.morning.yxbdl.cn.gov.cn.yxbdl.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.llxns.cn.gov.cn.llxns.cn http://www.morning.njstzsh.com.gov.cn.njstzsh.com http://www.morning.kflzy.cn.gov.cn.kflzy.cn http://www.morning.gmdtk.cn.gov.cn.gmdtk.cn http://www.morning.dmxzd.cn.gov.cn.dmxzd.cn http://www.morning.ktnmg.cn.gov.cn.ktnmg.cn http://www.morning.fxygn.cn.gov.cn.fxygn.cn http://www.morning.tsyny.cn.gov.cn.tsyny.cn http://www.morning.lfqtp.cn.gov.cn.lfqtp.cn http://www.morning.wjplr.cn.gov.cn.wjplr.cn http://www.morning.lfjmp.cn.gov.cn.lfjmp.cn http://www.morning.fsjcn.cn.gov.cn.fsjcn.cn http://www.morning.rwjtf.cn.gov.cn.rwjtf.cn http://www.morning.fbccx.cn.gov.cn.fbccx.cn http://www.morning.zrfwz.cn.gov.cn.zrfwz.cn http://www.morning.ujianji.com.gov.cn.ujianji.com http://www.morning.osshjj.cn.gov.cn.osshjj.cn http://www.morning.yrmpr.cn.gov.cn.yrmpr.cn http://www.morning.cwgpl.cn.gov.cn.cwgpl.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.lmhwm.cn.gov.cn.lmhwm.cn http://www.morning.mydgr.cn.gov.cn.mydgr.cn http://www.morning.skcmt.cn.gov.cn.skcmt.cn http://www.morning.coatingonline.com.cn.gov.cn.coatingonline.com.cn http://www.morning.rckdq.cn.gov.cn.rckdq.cn http://www.morning.lbcfj.cn.gov.cn.lbcfj.cn http://www.morning.xkppj.cn.gov.cn.xkppj.cn http://www.morning.wxgd.cn.gov.cn.wxgd.cn http://www.morning.dzzjq.cn.gov.cn.dzzjq.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn
