题目
思路
只把反色的边拿出来,构建成一片森林,那么最少的路径数即为奇数度数点的一半。
证明:
偶数点必然不能作为路径起点,因为如果作为起点,那么该点必然剩余奇数条出边,那么必然还有至少另外一条路径以该点为顶点,那么将这两条路径合二为一显然更优。
所以只有奇数点能作为路径起点,而显然任意奇数点最少需要成为一条路径的顶点,然后连边后所有度数为奇数的点变为度数为偶数的点,此时正好无法连边。
由于两个顶点组成一条路径,所以路径数即为奇数度数的点数的一半。
所以考虑树形 dp。设 \(f[x][0/1]\) 表示点 \(x\) 的子树内,\(x\) 与其父亲的边是否反色的最少路径数以及此时最少反色边数。那么记 \(p0,p1\) 分别表示 \(x\) 是否有个儿子与自己的路径反色的最小答案,那么可以分类讨论进行转移。
时间复杂度 \(O(n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010,Inf=1e9;
int n,tot,head[N];
struct edge
{
int next,to,id;
}e[N*2];
struct node
{
int x,y;
friend node operator +(node x,node y)
{
return (node){x.x+y.x,x.y+y.y};
}
}f[N][2];
node Min(node x,node y)
{
if (x.x<y.x) return x;
if (x.x>y.x) return y;
return (x.y<y.y)?(x):(y);
}
void add(int from,int to,int id)
{
e[++tot].to=to;
e[tot].id=id;
e[tot].next=head[from];
head[from]=tot;
}
void dfs(int x,int fa,int id)
{
node p0=(node){0,0},p1=(node){Inf,Inf};
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa)
{
dfs(v,x,e[i].id);
node p00=Min(p0+f[v][0],p1+f[v][1]);
node p11=Min(p0+f[v][1],p1+f[v][0]);
p0=p00; p1=p11;
}
}
f[x][0]=Min(p0,(node){p1.x+1,p1.y});
f[x][1]=Min((node){p0.x+1,p0.y+1},(node){p1.x,p1.y+1});
if (id==0) f[x][0]=(node){Inf,Inf};
if (id==1) f[x][1]=(node){Inf,Inf};
}
int main()
{
int size = 256 << 20; //250M
char*p=(char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p) );
memset(head,-1,sizeof(head));
scanf("%d",&n);
for (int i=1,u,v,a,b;i<n;i++)
{
scanf("%d%d%d%d",&u,&v,&a,&b);
if (b==2) add(u,v,2),add(v,u,2);
else add(u,v,a^b^1),add(v,u,a^b^1);
}
dfs(1,19260817,114514);
printf("%d %d",f[1][0].x/2,f[1][0].y);
return 0;
}