100.0% (4/4)

68.8% (11/16)

# Description

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
ll norm(ll &s)
{
return ((s%M)+M)%M;
}
struct dp
{
ll v,s,w[2],c[2];
dp(ll k) : v(k), s(k), w{0,k}, c{0,1} {}
dp operator += (const dp & r)
{
s = norm(s + r.s + w[0] * r.c[1] + w[1] * r.c[0] + r.w[0] * c[1] + r.w[1] * c[0]);
w[0] = norm(w[0] + r.w[1] - v * r.c[1]);
w[1] = norm(w[1] + r.w[0] + v * r.c[0]);
c[0] = norm(c[0] + r.c[1]);
c[1] = norm(c[1] + r.c[0]);
return *this;
}
};
const int N = 2e5 + 98;
ll v[N];
vector<int> g[N];
dp dfs(int p,int u)
{
dp now(v[u]);
for (int w : g[u])
if (w != p)
now += dfs(u,w);
return now;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i];
v[i] = norm(v[i]);
g[i].clear();
}
for (int i = 0; i < n-1; ++i) {
int u,v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
cout << norm(dfs(0,1).s * 2) << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
solve();
}


# Sample Input 1

2
4
-4 1 5 -2
1 2
1 3
1 4
8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

40
4