P2015 二叉苹果树

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

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

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

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

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

错误日志：保留和去掉看错了QAQ

Solution

树上背包

将边权下放到远离根节点的点上

保留 \(Q\) 条边等价于保留 \(Q +1\) 个节点，其中必选根节点

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 100019,INF = 1e9 + 19;

int head[maxn],nume = 1;

struct Node{

    int v,dis,nxt;

    }E[maxn << 3];

void add(int u,int v,int dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

int num, Q;//保留包括根节点之内的Q + 1个点

int val[maxn];

int dp[maxn][219];

int dfs(int u, int F){

	int size = 1;

	dp[u][0] = 0;

	for(int i = head[u];i;i = E[i].nxt){

		int v = E[i].v;

		if(v == F)continue;

		val[v] = E[i].dis;

		int t = dfs(v, u);

		size += t;

		for(int j = Q;j >= 0;j--){//枚举

			REP(k, 0, t){

				if(j >= k)

					dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);

				}

			}

		}

	for(int i = min(size, Q);i >= 1;i--)

		dp[u][i] = dp[u][i - 1] + val[u];

	return size;

	}

int main(){

	num = RD(), Q = RD();

	Q += 1;

	REP(i, 1, num - 1){

		int u = RD(), v = RD(), dis = RD();

		add(u, v, dis), add(v, u ,dis);

		}

	dfs(1, -1);

	printf("%d\n", dp[1][Q]);

	return 0;

	}

秒客网

P2015 二叉苹果树

P2015 二叉苹果树

Solution

Code

相关文章