w
题目背景
(frac 14)遇到了一道水题，双完全不会做，于是去请教小( ext{D})。小( ext{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)表示最终要求为白色、要求为黑色、没有要求。
输出格式
输出一行，两个整数，表示最小操作数、操作数最小时的最小路径长度和。
数据范围
(nin [1,10^5])，(a,bin [1,n])，(cin {0,1})，(din {0,1,2})
| ( ext{Subtask}) | 分值 | (nle) | 其他限制 |
|---|---|---|---|
| (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 ot=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))
如果可以翻转可以不翻转，就做两个有决策的
然后就没了
考虑可以从这个题目得到什么收获。
- 可以把最优状态下的最优压在一起拿二元组做
- 首先要认真研究性质，作为划分状态的依据
- 与路径有关的状态划分基于是否从头顶伸出一条边
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
",dp[1][0].c1>>1,dp[1][0].c2);
return 0;
}
2018.10.12