本文主要是介绍#树形dp#jzoj 1824 debug，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
删去最少的边，使每个节点的度不超过2。
分析
考虑一个邻接点不是叶子节点的点，那么优先选择割断与父亲节点的边。
why？
First：如果该点只有一个叶子节点，那么删去与叶子节点的边不需要这么做
Second：如果该点有多个叶子节点，保留一条原来被删除与叶子节点之间的边，得到的仍然是一个最优解
所以就可以构造出算法，从最下方的非叶子节点开始，当度超过2，那么累加删去的边，并使父亲节点的边减少，并继续搜父亲节点。
代码
#include <cstdio>
#include <cctype>
using namespace std;
struct node{int y,next;}e[200001]; bool v[100001];
int n,m,tot,ls[100001],deg[100001];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void dp(int x,int fa){v[x]=1;if (deg[x]==1&&e[ls[x]].y==fa) return;for (int i=ls[x];i;i=e[i].next)if (!v[e[i].y]) dp(e[i].y,x);if (deg[x]>2) tot-=deg[x]-2,deg[fa]--;
}
int main(){n=in(); tot=n-1; int x,y;for (int i=1;i<n;i++){deg[x=in()]++; deg[y=in()]++;e[++m]=(node){y,ls[x]}; ls[x]=m;e[++m]=(node){x,ls[y]}; ls[y]=m;}dp(1,0);return !printf("%d",tot);
}
这篇关于#树形dp#jzoj 1824 debug的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
