首页 > 其他分享 >[ARC183D] Keep Perfectly Matched

[ARC183D] Keep Perfectly Matched

时间:2024-08-26 10:04:12浏览次数:14  
标签:子树 匹配 ARC183D int siz top pos Perfectly Matched

My Blogs

[ARC183D] Keep Perfectly Matched

这场不打感觉亏麻了,怎么大家都不会 D。首先匹配路径长度之和最大,很典的想到取重心,猜测答案上界 \(\sum_i dep_i\) 可以取到。

取完重心之后,希望不断把两个不同的子树里的点进行匹配,直到删空。因为原树本身存在完美匹配,所以找一对不同子树里的点删去后,根节点的匹配一定变了。

所以选的点一定有一个在根节点当前的匹配点的子树里,否则根节点没有理由更改匹配点。设这个点为 \(x\),则 \(x\) 一定满足:其到根的路径上,边的种类是“匹配边,非匹配边,匹配边...”,即:

image.png

图中标 \(1\) 的边是匹配边,可以发现删六号点是合法的,而删 \(8\) 号点的过程中会因为连续出现了两条非匹配边而寄掉。

这样确定了一个子树中的点,另一个点是可以任意选的。因为要尽量匹配对,所以另一个点应该选在除此之外的 \(siz\) 最大的子树里面。接下来根的匹配就是选的第二个子树中的根节点。继续做上述过程即可。

这样做为何能取到最优值:设 \(x\) 是根的初始匹配节点,首先第一次删点的两棵子树一定分别是 \((x,y)\),然后第二次因为此时根和 \(y\) 匹配,所以要删 \((y,z)\),以此类推,可以发现除了开始的 \(x\) 删了一个点,剩下的操作都是,选一个子树删两个点,然后跳到另一棵子树。

除了 \(x\) 子树大小是奇数,剩下的子树大小都是偶数,一开始 \(x\) 删了 \(1\) 就全部变成了偶数。所以不会有奇偶性不对的情况。如果跳到另一棵子树选择当前 \(siz\) 最大的,那就一定能够删空。因为此时根是树的重心,每个子树内需要的操作次数大小都不会超过 \(\frac m 2\),其中 \(m\) 是总操作次数,所以这样做一定不会爆掉。

现在的问题就是如何高效的找出当前能删掉的合法点。策略也很简单:对于点 \(x\) 来说,如果初始他的匹配是他的父亲,则他儿子可以按任意顺序一个一个删光。

如果初始他的匹配是他的某个儿子,则先把这个儿子全部删空时最优的。然后他的匹配就变成了他的父亲,他剩下的儿子可以任意排列。

可以 \(\text{dfs}\) 求出每个子树的后序遍历,如果有某个儿子和他匹配就优先向这个儿子走,这样可以求出每个点的合法操作序列。然后套用上述过程,总复杂度 \(\mathcal O(n\log n)\) 或者 \(\mathcal O(n)\)。

int n,rt,minn=inf,len,ans[500010],siz[250010];
vi T[250010],ve[250010];
void findrt(int x,int fa=0)
{
	int maxn=0;siz[x]=1;
	for(auto to:T[x])if(to!=fa)
	findrt(to,x),siz[x]+=siz[to],Mmax(maxn,siz[to]);
	if(Mmin(minn,max(n-siz[x],maxn)))rt=x;
}
void dfs(int x,int fa,int top)
{
	ve[top].eb(x);
	for(auto to:T[x])if(to!=fa&&to!=(((x-1)^1)+1))dfs(to,x,top);
	if(fa!=(((x-1)^1)+1))dfs(((x-1)^1)+1,x,top);
}
priority_queue<pii> q;
inline void mian()
{
	read(n);int x,y;pii p;
	for(int i=1;i<n;++i)read(x,y),T[x].eb(y),T[y].eb(x);
	findrt(1),findrt(rt);
	for(auto to:T[rt])dfs(to,rt,to);
	int pos=((rt-1)^1)+1;ans[++len]=ve[pos].back(),ve[pos].pop_back(),--siz[pos];
	for(auto to:T[rt])q.e(mp(siz[to],to));
	for(int I=1;I<(n>>1);++I)
	{
		if(q.top().se==pos)p=q.top(),q.pop();else p=mp(-1,-1);
		pos=q.top().se;
		ans[++len]=ve[pos].back(),ve[pos].pop_back();
		ans[++len]=ve[pos].back(),ve[pos].pop_back();
		siz[pos]-=2;
		q.pop(),q.e(mp(siz[pos],pos));
		if(p.fi!=-1)q.e(p);
	}
	for(auto to:T[rt])if(siz[to])ans[++len]=to;
	ans[++len]=rt;
	for(int i=1;i<=len;i+=2)write(ans[i],' ',ans[i+1],'\n');
}

标签:子树,匹配,ARC183D,int,siz,top,pos,Perfectly,Matched
From: https://www.cnblogs.com/WrongAnswer90/p/18380150

相关文章

  • Vivado 12-508错误(即“No pins matched”)如何解决?
     时序约束时,vivado自动能找到的时钟,是IP核最内部的引脚,综合会出现报错,所以需要手动调整XDC文件,写顶层模块名和顶层能看到的引脚名称。 以下是文心一言的回答: 如果引脚是IP核(知识产权核)内部的,并且IP核在综合阶段被当作黑盒子处理,导致vivado12-508错误,如何解决呢? 如果引......
  • 机器学习策略篇:详解数据分布不匹配时,偏差与方差的分析(Bias and Variance with mismatc
    详解数据分布不匹配时,偏差与方差的分析估计学习算法的偏差和方差真的可以帮确定接下来应该优先做的方向,但是,当训练集来自和开发集、测试集不同分布时,分析偏差和方差的方式可能不一样,来看为什么。继续用猫分类器为例,说人类在这个任务上能做到几乎完美,所以贝叶斯错误率或者说贝叶......
  • ABC 307 D Mismatched Parentheses
    题解现在有个长度为N的字符串s,其中s由(,)和小写字母组成,每个)都要与其左边的(配成一对,并且将他们和中间的部分给删除掉。输出最后的s思路我们首先设最后的答案为空串,然后模拟整个过程就行了,一旦遇到(,我们就用cnt进行计数。一旦遇到),就在答案里一直删直到遇到最近的(为止。其......
  • 解释一下 "*.ts?(x)": [ "prettier --no-error-on-unmatched-pattern --cache --parse
    这段配置来自于一个项目的构建工具(如ESLint、Gulp、Webpack等)或者是一个任务运行器(如npmscripts、Makefile、gulpfile.js等)中的脚本命令,它通常是在lint-staged、husky等预提交钩子(GitHooks)配置中用来指定对特定类型文件进行格式化的指令。具体来说:"*.ts?(x)":这是一个glob......
  • WHEN NOT MATCHED THEN语句在oracle中的用法
    WHENNOTMATCHEDTHEN这是一个在某些数据库系统(如Oracle)中使用的特殊子句,用于处理左连接中的"未匹配"情况。当左连接的条件不满足时,这部分的代码会执行。在这种情况下,如果O.DCSHYBH的值在L中没有匹配项,那么将插入一个NULL值或默认值。总的来说,这段代码执行了一个左连接操作,并根......
  • 基于vue-router的matched实现面包屑功能
    如上图所示,就是常见的面包屑效果,面包屑的内容一般来说,具有一定的层级关系,就以上图为例,首先是进入首页,然后点击左侧导航,进入活动管理下的活动列表页面,然后点击某一条数据,进入活动详情页面这正好与vue-router的mached属性所获取的结果有着相似的原理,所以可以基于此来实现面包屑效......
  • Perfectly Clear Workbench(图片编辑软件)mac/win
    PerfectlyClearWorkBench是一款由AthentechImaging开发的图像校正软件,它提供了高效、自动化的图像颜色和曝光校正工具。该软件可以使用各种算法对图像进行智能分析和处理,以确保最佳视觉结果。Mac版PerfectlyClearWorkbench下载Win版PerfectlyClearWorkbench中文版Perfe......
  • 解决vue2.0路由 TypeError: Cannot read property 'matched' of undefined 的错误问题
      找了很久这个问题 解决vue2.0路由TypeError:Cannotreadproperty'matched'ofundefined的错误问题-北桥苏-博客园(cnblogs.com)  解决办法改为   问题解决  没有找到为什么 好像高版本的router没有这个问题 我因为需要降级到了3.1.3 ......
  • Oracle ORA-12725 unmatched parentheses in regular expression
    OracleORA-12725unmatchedparenthesesinregularexpression简单来说就是正则表达式中的括号问题这种一般就可以锁定使用正则的函数,例如regexp_replace、regexp_lik......
  • Codeforces Round #716 (Div. 2) A. Perfectly Imperfect Array
    problemA.PerfectlyImperfectArraytimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputGivenanarrayaof......