zzuli 1907: 小火山的宝藏收益

***题意：中文的

做法：邻接表+DFS，就相当于搜一棵树，比较一下当前结点得到的宝藏多还是子树下面得到的宝藏多，仔细想想就是水题***

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long LL;
#define N 10100
#define INF 0x3f3f3f

struct node
{
    int v, next;
} maps[N<<2];
int a[N];
int head[N], k;
int vis[N];

void add(int u, int v)
{
    maps[k].v=v;
    maps[k].next=head[u];
    head[u]=k++;
}

int DFS(int s)
{
    int sum=0;
    vis[s]=1;
    for(int i=head[s]; i!=-1; i=maps[i].next)
    {
        int v=maps[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            sum+=DFS(v);
            //vis[v]=0;
        }
    }
    return max(a[s], sum);
}

int main()
{
    int T, n, s, u, v;
    scanf("%d", &T);

    while(T--)
    {
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        k=0;
        scanf("%d%d", &n, &s);
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        for(int i=1; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        vis[s]=1;
        printf("%d
", DFS(s));
    }
    return 0 ;
}