End Credits

news/2024/7/3 2:42:19

我不知道怎么把他删掉...

今晚WC文艺汇演wwww(等待唱歌.jpg

要是能截到屏一定发上来qwqqqqq

话说这首曲子是新发现的QAQ(Xeuphoria的还是那么好听qwqqq

今天学了快读qvq

还有...dpwww

P2015 二叉苹果树

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2   5\ / 3   4\ /1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

这是一道树dp。。

然而我dp最差了qwqqqqqqq

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<cmath>
#define mod 1010
using namespace std;
typedef long long ll;
int n,q;
int f[mod][mod];//f[i][j]表示节点i保留j个枝条的所剩苹果最大值QAQ
int head[mod],x,y,z,cnt,b[mod];int read()
{int ans = 0,op = 1;char ch = getchar();while(ch < '0' ||ch > '9'){if(ch == '-')op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op;
}struct edge
{int next,to,v;
}e[mod];void add(int x,int y,int z)
{++cnt;e[cnt].to = y;e[cnt].v = z;e[cnt].next = head[x];head[x] = cnt;
}
void dfs(int x,int dad)
{for(int i = head[x];i;i = e[i].next){int k = e[i].to;if(k == dad)//如果下一个相邻节点就是父节点，就证明到底层了，递归父节点的兄弟节点
       {continue;}dfs(k,x);b[x] += b[k] + 1;for(int p = min(q,b[x]);p>=1;--p)//限制枝条数目qwq 
       {for(int j = min(b[k],p-1);j >= 0;--j){f[x][p] = max(f[x][p],f[x][p-j-1]+f[k][j]+e[i].v );}}}
}int main(){n = read();q = read();for(int i = 1;i <= n-1;++i){x = read();y = read();z = read();add(x,y,z);add(y,x,z);//双向边qaq 
    }dfs(1,0);printf("%d\n",f[1][q]);return 0;
}