安徽建设银行官方网站,常用的网络推广方式有哪些,四库一平台查询入口,做电影网站前途一开始状态定义错了……所以没有对qwq#xff0c;以及有几个坑qwq…… 首先 f [ i ] [ j ] 表示以 i 为根的子树#xff0c;切除 j 个节点所需要切除的最小边数#xff0c;而我一开始定义的是表示以 i 为根的子树#xff0c;切除后生成一颗有 j 个节点的子树#xff0c;所… 一开始状态定义错了……所以没有对qwq以及有几个坑qwq…… 首先 f [ i ] [ j ] 表示以 i 为根的子树切除 j 个节点所需要切除的最小边数而我一开始定义的是表示以 i 为根的子树切除后生成一颗有 j 个节点的子树所需要切除的最小边数。 为什么我的不行呐因为对于一个新的子节点更新状态它能生成多大的子树其实是和父亲节点是没有关系的即它与父亲节点原来的状态无关也两棵树不也连通然而对于切除多少点我们在意的是切除后剩的而不是切除的。那么最后的ans就是 f [ ... ] [ num - p ] f [ ... ] [ num [ ... ] ]了。 以及根节点的 f [ ] num是0因为它没有父亲节点本身就是一颗含有 num 个点的子树。 代码如下 #includecstdio
#includeiostream
#includecstring
#includealgorithm
using namespace std;
#define maxn 2000
struct node
{int to,nxt;
} edge[maxn];
int f[maxn][maxn],num[maxn],head[maxn];
int n,p,cnt,ans999999999;
void add(int a,int b)
{edge[cnt].tob;edge[cnt].nxthead[a];head[a]cnt;
}
void dfs(int u,int fa)
{num[u]1;for(int ihead[u]; i; iedge[i].nxt){int tot0,am0;int vedge[i].to;if(vfa) continue;dfs(v,u);num[u]num[v];f[u][num[v]]1;amnum[v];f[u][am]tot;}f[u][num[u]]1;f[u][0]0;if(u1) f[u][num[u]]0;
}
void dp(int u,int fa)
{for(int ihead[u]; i; iedge[i].nxt){int vedge[i].to;if(vfa) continue;dp(v,u);for(int jnum[u]; j0; j--)for(int k0; kj; k)f[u][j]min(f[u][j],f[u][j-k]f[v][k]);}if(num[u]p)ansmin(ans,f[u][num[u]-p]f[u][num[u]]);
}
int main()
{memset(f,0x3f3f3f3f,sizeof(f));scanf(%d%d,n,p);for(int i1; in; i){int x,y;scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(1,0);dp(1,0);printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/popo-black-cat/p/10337025.html
