题目链接:
咕
闲扯:
这题考场上把子任务都敲满了,5个namespace,400行11k
结果爆0了哈哈,因为写了个假快读只能读入一位数,所以手测数据都过了,交上去全TLE了
把边分成三类:0. 需要染色的 1. 不需要染色的 2. 染不染色无所谓
考场上首先发现一个性质,就是一定存在一种最优解没有染任何一条本来不需要的染色边。
为啥?其实也挺显然的,因为你染色跨过这条边还得染这条边一次,不如直接只染左右的联通块,这样总路径长度还能更小
但是第三种边的呢?有个子任务就是枚举它染不染。
然后链上的情况就搞了个贪心的做法,如果对于一条第三种情况的边,如果两边的联通块是需要染色的,显然选这条边是更优的.但是注意考虑多条这种边连在一起的情况.
然后树上的版本贪心似乎就GG了
然后晚上盯着毫无注释std和仅有三行的题解,画了一面的草稿纸,终于看懂了…
分析:
首先我们需要假如我们已经有了最优情况的一种边集,怎么求出最小操作次数,其实是边集的点集中度数为奇数的点的个数除以2。为什么?显然最优情况下,每一个奇数度数点恰好是一条操作路径的结尾，由于一条操作路径连接两个点所以除以2
然后对于一个以x为根的子树,如果已经取得了最优解,可以通过分情况考虑更新父亲,显然是具有最优子结构的.于是使用树形DP
定义$f[x][0/1]$表示在以x为根的子树中,不染色/染色x与其父亲相连的最优代价
(注意代价是一个二元组$cost(x,y)$代表奇数点个数和染色路径总长度,这里比较代价大小根据题意,就不赘述了)
为了分情况转移我们需要求出两个值,$npt$是x在x为根的子树中假如x不是任意一条染色路径的端点的最优代价；$pt$是x在x为根的子树中假如x是某一条染色路径的端点时的最优代价（注意这里的路径端点都是从子树引出来的路径）
怎么求出$npt$和$pt$呢?我们可以将所有$x$的儿子$v$回溯到$x$的过程中逐个统计,接下来比较神奇可以借助图像理解
$npt=min(npt+f[v][0],pt+f[v][1])$
解释: 画图,若$v$到其父亲$x$边没有染色,说明原来如果x不是路径端点的话现在还不会是端点;类似的,若$v$到父亲$x$的边染色了,并且$x$此时是一条路径的端点,那么这时候我们可以把路径延长到$v$的子树中,这样是解更优并且$x$这样就不会是路径端点了
$pt = min(npt+f[v][1],pt+f[v][0])$
解释:与上面类似就太懒不想打了,有问题可以luogu或QQ联系我
在考虑DP中$f$数组的转移
再强调一下定义:定义$f[x][0/1]$表示在以x为根的子树中,不染色/染色x与其父亲相连的最优代价
设$x$与其父亲相连的边的属性为$p$
首先根据在”闲扯”中的性质以及题意,若$p=1,f[now][1]=(inf,inf)$;若$p=0,f[now][0]=(inf,inf)$
然后现在先考虑$f[now][0]$,$f[now][0]=min(npt,cost(pt.x+1,pt.y))$ , 这里的$cost$可以理解为$make$_$pair$
解释:如果$x$不是染色路径的端点,而且x到父亲的边也不染色,那么显然代价不变.但是如果$x$是某一条路径的端点,那么这时候我们需要加上$x$这个点的贡献(它是个端点那肯定是奇数度数)
再考虑$f[now][1],f[now][1]=min(cost(npt.x+1,npt+1),cost(pt.x,pt.y+1))$
解释:如果$x$不是路径端点,那么$x$如果和父亲相连的边染色的需要新开一条路径,所以见上；如果$x$是路径端点,那么我们可以把这条路径引上去,x点的贡献就不用计算,只需要让路径长度加1就好了
然后就没了,代码很短但很难想
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <vector>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=100005;
const int inf=0x7ffffff;
struct Edge{
int ne,to,w;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to,int x){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
edge[num_edge].w=x;
h[f]=num_edge;
}
struct Dat{
int x,y;
Dat(){x=y=inf;}
Dat(int _x,int _y){x=_x,y=_y;}
Dat operator +(const Dat &b)const{
return Dat(x+b.x,y+b.y);
}
bool operator <(const Dat &b)const{
return x==b.x?y<b.y:x<b.x;
}
}f[maxn][2];
int n;
void dfs(int now,int fa,int t){
int v;
Dat npt=Dat(0,0),pt=Dat(inf,inf);
Dat pa=Dat(0,0),pb=Dat(0,0);
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(v==fa)continue;
dfs(v,now,edge[i].w);
pa=min(npt+f[v][0],pt+f[v][1]);
pb=min(npt+f[v][1],pt+f[v][0]);
npt=pa,pt=pb;
}
if(t==1)f[now][0]=Dat(inf,inf);
else {
f[now][0]=min(npt,Dat(pt.x+1,pt.y));
}
if(t==0)f[now][1]=Dat(inf,inf);
else {
f[now][1]=min(Dat(npt.x+1,npt.y+1),Dat(pt.x,pt.y+1));
}
return;
}
int main(){
int x,y,c,d;
freopen("w.in","r",stdin);
freopen("w.out","w",stdout);
read(n);
for(ri i=1;i<n;i++){
read(x),read(y),read(c),read(d);
if(d==2){
add_edge(x,y,2),add_edge(y,x,2);
}
else {
d=c^d;
add_edge(x,y,d),add_edge(y,x,d);
}
}
dfs(1,0,0);
Dat ans=min(f[1][0],f[1][1]);
printf("%d %d\n",ans.x/2,ans.y);
return 0;
}
|