【zzuliOJ】1907 - 小火山的宝藏收益（dfs）

FishWang

发布于 2025-08-27 10:04:22

13100

代码可运行

运行总次数：0

代码可运行

点击打开题目

1907: 小火山的宝藏收益

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 108 Solved: 23 Submit Status Web Board

Description

进去宝藏后，小火山发现宝藏有N个房间，且这n个房间通过N-1道门联通。

每一个房间都有一个价值为Ai的宝藏，但是每一个房间也都存在一个机关。如果小火山取走了这个房间的宝藏，那么这个房间通往其他房间的门就永远打不开了，也就是说后面的宝藏小火山是得不到了（进入这个房间的门是不会关闭的，小火山还是可以回去的）；如果小火山不取这个宝藏，而是去打开通往另一房间的门，那么这个房间的宝藏就会消失，小火山就得不到这个房间的宝藏。

不过，小火山已经有了藏宝图，知道每一个房间的宝藏的价值，现在想请你帮小火山算一下，他最多能获得多少钱去买股票？

Input

输入第一行是一个整数T（T <= 50), 表示一共有T组数据。

对于每一组数据，第一行是两个数N, S（1 <= N <= 10000, 1 <= S <= N), N代表有N个房间， S代表小火山进去宝藏后的

起始房间（小火山怎么进入起始房间不重要），第二行是N个数，代表每个房间宝藏的价值，随后N-1行，每行两个数A, B，代表

A, B这两个房间联通。

Output

对于每一组数据输出一个整数，代表小火山能获得的最大钱数。

Sample Input

1 1

3 1

4 5 6

1 2

2 3

Sample Output

206

HINT

Source

zzuli

在图上从根节点跑一遍dfs，统计它的枝叶的最大和与本身取最大值就行了。

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
vector<int> mapp[10011];
int v[10011];
void dfs(int root,int fa)
{
    if (mapp[root].size() == 1 && mapp[root][0] == fa)
        return;
    int sum = 0;
    for (int i = 0 ; i < mapp[root].size() ; i++)
    {
        int c = mapp[root][i];
        if (c != fa)
        {
            dfs(c,root);
            sum += v[c];
        }
    }
    v[root] = max (v[root] , sum);
}
int main()
{
    int u;
    int n,s;
     
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d",&n,&s);
        for (int i = 1 ; i <= n ; i++)
        {
            scanf ("%d",&v[i]);
            mapp[i].clear();
        }
        for (int i = 1 ; i < n ; i++)
        {
            int t1,t2;
            scanf ("%d %d",&t1,&t2);
            mapp[t1].push_back(t2);
            mapp[t2].push_back(t1);
        }
        dfs(s,s);
        printf ("%d\n",v[s]);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs