ACM►学习笔记►图论

树的最小路径覆盖

用最少条数的路径覆盖树，这是一个树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