Ric_shooter
ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 1.
Remilia
posted @ 2019年2月19日 21:08
in 涂字
, 290 阅读
ABCDEFGHIJKL
Problem J:
给出一棵N个叶子的无根二叉树.定义一个四元组(A,B,C,D)(A,B,C,D都是叶子且互不相同)是good的,当存在一条分割边,使得A,B在一个子树中,C,D在另一个子树中.AB与BA是相同的,CD与DC是相同的,AB|CD与CD|AB是相同的.现在给出两棵树,求两棵树所有四元组构成的集合对称差的大小。N<=2000
Sol:首先对称差问题可以转化为求集合的交.
A,B,C,D都是叶子,则任意A,B,C,D恰好只有一种划分方案是合法的.现在考虑给树定根,枚举两棵树中的各一个点i,j,使其为四元组一对点的LCA,而另外两个点就在子树外取到.这样只需要三次矩阵数点就可以完成.利用前缀和可以O(1)求解.
然而这样做会有一些问题.若两对点的LCA为祖父关系,则会被恰好计算一次,否则会被计算两次.我们需要通过某种方式使得每种方式都被计算相同的次数.
那么考虑将树作为无根树考虑.对于每对关系,必定存在两条边,使得这两条边各存在一种定向的方法使得答案被算到一次.于是枚举每条边以及该边的定向,暴力计算内即可.时间复杂度O(N^2),常数略大.
2024年1月25日 14:55
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. <a href="https://pavzi.com/">pavzi.com</a> Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.
2024年1月25日 14:56
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.