树的最小路径覆盖

用最少条数的路径覆盖树,这是一个树dp问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int u,int father){
int sum=0;
for(int i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
dfs(edge[i].v,u);
sum+=dp[edge[i].v][0];
}
dp[u][0]=sum+1;//子树路径覆盖的答案
dp[u][1]=sum+1;
vector<int>update;
for(int i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
update.push_back(-dp[edge[i].v][0]+dp[edge[i].v][1]-1);
}
sort(update.begin(),update.end());
if(update.size()>=1) {
if(update[0]<0) dp[u][0]+=update[0];
if(update[0]<0) dp[u][1]+=update[0];
}
if(update.size()>=2){
if(update[1]<0) dp[u][0]+=update[1];
}
}// dp[root][0] is min path cover the tree