树上博弈

做法：状压dp

思路

每个点与附近连边的点用二进制状态表示，1表示有边，0表示无边
该状态选取的点也用二进制状态表示，1表示选了，0表示没选
选取该点的值后的差值为该点的值减去转移前的差值

代码

// Problem: 树上博弈
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9985/E
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=21;
const ll INF=1e18;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

ll a[N],e[N],dp[1<<N];

void solve(){
    int n;cin>>n;
    rep(i,0,n-1) cin>>a[i],e[i]=0;
    _for(i,(1<<n)) dp[i]=-INF;
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        u--,v--;
        e[u]|=(1<<v);
        e[v]|=(1<<u);
    }
    rep(i,0,n-1) dp[1<<i]=a[i];
    rep(i,1,(1<<n)){
        if(dp[i]!=-INF){
            rep(j,0,n-1){
                if(!(i&(1<<j))&&(i&e[j])) dp[i|(1<<j)]=max(dp[i|(1<<j)],a[j]-dp[i]);
            }
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}