poj 4313 Matrix 夜

http://acm.hdu.edu.cn/showproblem.php?pid=4313

一遍dfs   注意值的传递就可以了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<cmath>
#define LL long long

using namespace std;

const int N=100010;
const int M=1000000000;
struct node
{
    LL sum;
    struct tt *next;
}mem[N];
bool machine[N];
struct tt
{
    int j;
    int k;
    struct tt *next;
};
LL Mmax(LL a,LL b)
{
    if(a>b)
    return a;
    return b;
}
LL Mmin(LL a,LL b)
{
    if(a<b)
    return a;
    return b;
}
void build(int i,int j,int k)
{
    struct tt *t=new tt;
    t->j=j;
    t->k=k;
    t->next=mem[i].next;
    mem[i].next=t;
}
void Dele(int n)
{
    for(int i=0;i<n;++i)
    mem[i].next=NULL;
}
LL dfs(int pre,int x)
{
    //cout<<x<<endl;
    struct tt *t=mem[x].next;
    bool flag=false;
    mem[x].sum=0;
    LL sumtemp=0;
    LL Msum=0;
    while(t!=NULL)
    {
        if(t->j==pre)
        {t=t->next;continue;}
        flag=true;
        LL a;
        a=dfs(x,t->j);
        a=Mmin(a,(LL)(t->k));
        sumtemp+=a;
        Msum=Mmax(Msum,a);
        mem[x].sum+=mem[t->j].sum;
        t=t->next;
    }
    if(flag==false)
    {//cout<<x<<" "<<mem[x].sum<<endl;
        if(machine[x]==true)
        return M;
        return 0;
    }
    mem[x].sum+=sumtemp;
    if(machine[x]==true)
    {//cout<<x<<" "<<mem[x].sum<<endl;
        return M;
    }else
    {
        mem[x].sum-=Msum;
        return Msum;
    }
}
int main()
{
    //freopen("data.txt","r",stdin);
    int T;
    scanf("%d",&T);
    int n,m;
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<n;++i)
        {
            int x,y,k;
            scanf("%d %d %d",&x,&y,&k);
            build(x,y,k);
            build(y,x,k);
        }
        memset(machine,false,sizeof(machine));
        while(m--)
        {
            int x;
            scanf("%d",&x);
            machine[x]=true;
        }
        dfs(-1,0);
        cout<<mem[0].sum<<endl;
        Dele(n);
    }
    return 0;
}