专用主机网站建设,软件开发和网站建设哪个好,绍兴优化公司,电商推广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
