当前位置: 首页 > news >正文

网站建设hph下载旅游网站哪家好又便宜

网站建设hph下载,旅游网站哪家好又便宜,专做智能化施工的网站,山东建设厅官方网站孙松青Description 给出两棵 n 结点的有标号树。 每次操作删去第一棵树的一条边#xff0c;再加上一条边#xff0c;需要保证此时还是一棵树。 构造一种操作序列#xff0c;将第一棵树变成第二棵树#xff0c;使得操作数最小。 n ≤ 51055 \times 10^55105 Solution 显然…Description 给出两棵 n 结点的有标号树。 每次操作删去第一棵树的一条边再加上一条边需要保证此时还是一棵树。 构造一种操作序列将第一棵树变成第二棵树使得操作数最小。 n ≤ 5×1055 \times 10^55×105 Solution 显然对于第一颗树的边x↔yx \leftrightarrow yx↔y如果这条边在第二颗树中也存在那么是不可能更改这条边的。一个朴素的想法是直接遍历第一颗树如果当前节点和其父亲连的边在第二颗树中没出现那么更改为连向第二颗树中的父节点。但这样会产生一个问题如果第二棵树的父节点在第一颗树中变成了子节点那么这条边也留着所以不能直接连父节点否则会出现环考虑把用两棵树之间相同的边连接起来的点缩成一个点因为两棵树都有的边无需改变所以我们这样做对题目没什么影响我们称这缩点后的点为大点可以发现第一棵树除了根大点外每个大点中深度最低的那个小点与父节点之间的边是要被改变的而他们要改成的边是第二棵树中这个大点中深度最低的点与父节点之间的边所以我们考虑用并查集来做每个大点即一个并查集并查集的根为第二棵树中要改变的点。然后在dfs第一棵树时如果遇见不在第二棵树中的边查询当前节点所在并查集中的根将第一棵树中这个节点和父节点之间的边改成它所在并查集的根与它在第二棵树中父节点之间的边。注意一颗树中出现环当且仅当一个点和它父节点连的边更改成和它的子树节点连所以我们从叶子节点往上更新就可以保证不会在操作过程中出现环即在dfs时要先处理子节点再处理当前节点。 Code #includeiostream #includecstdio #includevector using namespace std; const int N5e55; struct Edge{int v,nxt; }e1[N1],e2[N1]; int n,head1[N],cnt1,head2[N],cnt2,fa1[N],fa2[N]; int bel[N]; struct Ans{int a,b,c,d;}; vectorAns ans; void add1(int u,int v){e1[cnt1].vv;e1[cnt1].nxthead1[u];head1[u]cnt1; } void add2(int u,int v){e2[cnt2].vv;e2[cnt2].nxthead2[u];head2[u]cnt2; } void dfs1(int u,int f){for(int ihead1[u];i;ie1[i].nxt){int ve1[i].v;if(vf) continue;fa1[v]u;dfs1(v,u);} } void dfs2(int u,int f){for(int ihead2[u];i;ie2[i].nxt){int ve2[i].v;if(vf) continue;fa2[v]u;dfs2(v,u);} } int find(int x){if(bel[x]x) return x;return bel[x]find(bel[x]); } void rebuild(int u){for(int ihead1[u];i;ie1[i].nxt){int ve1[i].v;if(vfa1[u]) continue;rebuild(v);if(u!fa2[v]v!fa2[u])ans.push_back((Ans){u,v,find(v),fa2[find(v)]});} } int main(){scanf(%d,n);int x,y;for(int i1;in;i){scanf(%d%d,x,y);add1(x,y);add1(y,x);}for(int i1;in;i){scanf(%d%d,x,y);add2(x,y);add2(y,x);}dfs1(1,0);dfs2(1,0);bel[1]1;for(int i2;in;i)bel[i](fa1[i]fa2[i]||fa1[fa2[i]]i)?fa2[i]:i;rebuild(1);printf(%d\n,ans.size());for(int i0;ians.size();i) printf(%d %d %d %d\n,ans[i].a,ans[i].b,ans[i].c,ans[i].d);return 0; }参考文章 https://blog.csdn.net/u014664226/article/details/50901616
http://wiki.neutronadmin.com/news/409124/

相关文章:

  • 网站初期内容wordpress文章归档
  • 怎么把网站放到百度第五次普查数据自网站怎么做
  • 常州网站建设机构展示型企业网站制作费用
  • wordpress接入翼支付宝seo网站运营
  • 网站开发定制公司国内wordpress主题商
  • 微网站的案例上海网站建设的价格低
  • 易网官方网站求个网站2021
  • 网站建设大型常见的微网站平台有哪些方面
  • 网站开发尾款如何做账免费推广软件
  • 合肥的网站建设公司想学设计师首先要学什么
  • 做视频网站怎么赚钱襄阳优化公司
  • 建设企业品牌网站推广网站的方法有搜索
  • 凡科网站代理登录入口建设厅网站上保存键看不见
  • 创业网站建设方案项目书千万别学计算机应用技术
  • 网站视频封面怎么做怎么修改wordpress布局
  • 口腔医院东莞网站建设做网站的需要考什么证书吗
  • 网站方案设计做网站还要做点手机吗
  • 保定网站建设公司哪家好企业名录搜索软件 2022
  • 简洁软件下载网站源码wordpress网站制作价格
  • 手机电脑网站旅游 网站开发的项目描述
  • 自己做国际网站wap网站和internet网站
  • 企业免费网站建设模板下载美工培训
  • 马克杯网站开发wordpress实时交流插件
  • 网络在线培训网站建设方案超溜网站建设
  • 餐饮网站建设公司网站分析设计做的项目的过程
  • 个人网站建设总结长沙本地烟
  • 网站底部的备案信息将wordpress文件上传
  • 公司培训网站需要广播证吗wordpress 主题添加标签
  • 网站表单制作ip域名找网站
  • 做交易网站需要用到的软件要建立网站是否要先做网页设计_然后把网页设计与数据库连接起来?