雅礼集训 Day3 T3 w 解题报告

时间:2022-03-16 22:59:20
雅礼集训 Day3 T3 w 解题报告

w

题目背景

\(\frac 14\)遇到了一道水题,双完全不会做,于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607^2\)眼就切掉了这题,嘲讽了\(\frac 14\)一番就离开了。

于是,\(\frac 14\)只好来问你,这道题是这样的:

题目描述

有一棵\(n\)个节点的树,每条边长度为\(1\),颜色为黑或白。

可以执行若干次如下操作:选择一条简单路径,反转路径上所有边的颜色。

对于某些边,要求在操作结束时为某一种颜色。

给定每条边的初始颜色,求最小操作数,以及满足操作数最小时,最小的操作路径长度和。

输入输出格式

输入格式

第一行,一个正整数\(n\)。

接下来\(n-1\)行,每行四个整数\(a,b,c,d\):

  • 树中有一条边连接\(a\)和\(b\)。

  • \(c=0,1\)表示初始颜色为白色、黑色。

  • \(d=0,1,2\)表示最终要求为白色、要求为黑色、没有要求。

输出格式

输出一行,两个整数,表示最小操作数、操作数最小时的最小路径长度和。

数据范围

\(n\in [1,10^5]\),\(a,b\in [1,n]\),\(c\in \{0,1\}\),\(d\in \{0,1,2\}\)

\(\text{Subtask}\) 分值 \(n\le\) 其他限制
\(1\) \(18\) \(20\)
\(2\) \(25\) \(10^3\) 最多\(10\)条边使得\(d=2\)
\(3\) \(23\) \(10^5\) 保证\(a+1=b\)
\(4\) \(1\) \(10^5\) 保证\(d=2\)
\(5\) \(13\) \(10^5\) 保证\(d\not=2\)
\(6\) \(20\) \(10^5\)

又是一道神题,先形式化的说一说做法吧。


有一个容易发现的小性质:每条边最多只需要翻转一次。

然后我们考虑翻转了边集\(E\),边集\(E\)的操作数为边集中连接的点的奇数度数点的个数除2,路径长度为边数。我们需要在最小化前者的基础上最小化后者。

可以把代价直接压进去做树形\(DP\),考虑每个子树的最小化代价。

子树划分为两个状态,代表头顶上的点是否翻转。

具体的说\(dp_{i,0/1}\)代表以\(i\)为根的子树具有最优代价(\(c_1,c_2\))时是否(0/1)翻转头顶的边,\(c_1\)为奇数点个数,\(c_2\)为翻转路径长度。

这里边,点的代价均下放。


考虑儿子集合\(\{v\}\)如何被转移。

\(w_1\)代表已经转移的集合\(\{v'\}\)有一条向\(i\)伸出的翻转边的最小代价,\(w_2\)代表没有伸出翻转边

\(w_1=min(w_1+dp_{v,0},w_2+dp_{v,1})\)

\(w_2=min(w_1+dp_{v,1},w_2+dp_{v,0})\)

也就是拿子树做了一个递推。

初始化:\(w_1=(inf,inf),w_2=(0,0)\)


考虑如何用\(w_1,w_2\)更新\(i\)的答案。

如果\(i\)的头顶一定需要翻转

\(dp_{i,0}=(inf,inf)\)

\(dp_{i,1}=min((w_1.c_1,w_1.c_2+1),(w_2.c_1+1,w_2.c_2+1))\)

分别代表 翻转向上延伸,奇数点不变,路径长度+1 和 独立翻转出去,奇数点与路径长均+1

如果\(i\)的头顶一定不需要翻转

\(dp_{i,0}=min((w_1.c_1+1,w_1.c2),w_2)\)

分别代表\(i\)成为奇数点,路径不变 和 直接没操作

\(dp_{i,1}=(inf,inf)\)

如果可以翻转可以不翻转,就做两个有决策的

然后就没了


考虑可以从这个题目得到什么收获。

  1. 可以把最优状态下的最优压在一起拿二元组做
  2. 首先要认真研究性质,作为划分状态的依据
  3. 与路径有关的状态划分基于是否从头顶伸出一条边

Code:

#include <cstdio>
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int head[N],to[N<<1],Next[N<<1],edge[N<<1],cnt,n;
void add(int u,int v,int w)
{
to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;
}
struct node
{
int c1,c2;
node(){}
node(int c1,int c2){this->c1=c1,this->c2=c2;}
node friend operator +(node n1,node n2)
{
node n3(n1.c1+n2.c1,n1.c2+n2.c2);
return n3;
}
bool friend operator <(node n1,node n2)
{
return n1.c1==n2.c1?n1.c2<n2.c2:n1.c1<n2.c1;
}
}dp[N][2];
node min(node n1,node n2){return n1<n2?n1:n2;}
void dfs(int now,int fa,int typ)
{
node w1(inf,inf),w2(0,0),nx1,nx2;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa) continue;
dfs(v,now,edge[i]);
nx1=min(w1+dp[v][0],w2+dp[v][1]);
nx2=min(w1+dp[v][1],w2+dp[v][0]);
w1=nx1,w2=nx2;
}
if(typ==1||typ==2)
dp[now][1]=min(node(w1.c1,w1.c2+1),node(w2.c1+1,w2.c2+1));
else
dp[now][1]=node(inf,inf);
if(typ==0||typ==2)
dp[now][0]=min(node(w1.c1+1,w1.c2),w2);
else
dp[now][0]=node(inf,inf);
}
int main()
{
scanf("%d",&n);
for(int a,b,c,d,i=1;i<n;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
c=d==2?d:c!=d;//0不翻转,1翻转,2随便
add(a,b,c),add(b,a,c);
}
dfs(1,0,2);
printf("%d %d\n",dp[1][0].c1>>1,dp[1][0].c2);
return 0;
}

2018.10.12