题解
奇数个点组成的路径才对答案有贡献
具体的解法是对每个点计算它对答案的贡献
每个点（设为$u$）对答案的贡献有两部分
- 路径中除$u$外所有点都是在$u$的子孙节点中
即在$u$的任意两个子树中各取一个点$v_1,v_2$，使$v_1,v_2$到$u$组成的路径同时有奇数个点或同时为偶数个点。这样从$v_1$到$v_2$，经过$u$的路径中含有奇数个点，能对答案有贡献，到$u$路径为奇数个点的做正贡献，为偶数的做负贡献。通过dfs可处理，（语言不好描述，详见代码）
设$odd[i]$为$i$点 自身 和的子孙节点中由该点到$i$组成的路径含有奇数个点的个数
$even[i]$为$i$点的子孙节点中由该点到$i$组成的路径含有偶数个点的个数 - 路径中一部分是$u$的祖先节点，一部分是$u$的子孙节点
这里有个重要结论
设$allodd[i],alleven[i]$为图中所有点中到该点组成路径含有奇数点（偶数点）的个数
设$1$为根节点,则
$$allodd[1]=odd[1]\\alleven[1]=odd[1]$$
同时若$u,v$为相邻的两个点
$$allodd[u]=alleven[v]\\alleven[u]=allodd[v]$$
设节点高度为$level[i],level[1]=1$
则$$\begin{cases}
allodd[i]=allodd[1]=odd[1],alleven[i]=alleven[i]=even[1] & level[i]\%2=1\\
allodd[i]=alleven[1]=even[1],alleven[i]=allodd[i]=odd[1] & level[i]\%2=0\\
\end{cases}$$
设 $upo,upe$：该点自身和祖先节点中到该点组成的路径含奇数（偶数）个点的点的个数。
$$upo=allodd[i]-odd[i]+1\\upe=alleven[i]-even[i]$$
此点的贡献为
$$
(allodd[i]\times odd[i]-alleven[i]\times even[i])\times 2\times val[i]-val[i]
$$
注意当路径长度为1时，只能做一次贡献，而式子中是乘以2的，答案最后应减去一个$val[i]$代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96//4 18
using namespace std;
typedef long long ll;
const ll MAXN=2e5+100;
const ll MOD=1e9+7;
struct Edge{
ll from,to,nxt;
}edge[MAXN*2];
ll eidx;
ll head[MAXN];
void addedge(ll from,ll to)
{
edge[eidx].from=from; edge[eidx].to=to;
edge[eidx].nxt=head[from]; head[from]=eidx++;
}
void einit()
{
eidx=0;
memset(head,-1,sizeof head);
}
ll val[MAXN];
ll o[MAXN],e[MAXN],lev[MAXN];
ll ans;
bool vis[MAXN];
void dfs(ll u,ll h,ll fa){
lev[u]=h;
vis[u]=1;
o[u]=e[u]=0;
for(ll i=head[u];i!=-1;i=edge[i].nxt)
{
ll v=edge[i].to;
if(vis[v]) continue;
dfs(v,h+1,u);
ll ta=2*(o[u]*e[v]%MOD-o[v]*e[u]%MOD)%MOD*val[u]%MOD;
ta=(ta%MOD+MOD)%MOD;
if(u==1)
{
//printf("ou %lld eu %lld ta %lld\n",o[u],e[u],ta);
}
ans=(ans+ta)%MOD;
o[u]+=e[v];
e[u]+=o[v];
}
o[u]++;
}
void init()
{
memset(vis,0,sizeof vis);
}
int main()
{
//freopen("input.txt","r",stdin);
ll n;
//while(cin>>n)
{
cin>>n;
einit();
init();
for(int i=1;i<=n;++i){
scanf("%lld",&val[i]);
}
for(int i=1;i<n;++i)
{
ll p1,p2;
scanf("%lld%lld",&p1,&p2);
addedge(p1,p2);
addedge(p2,p1);
}
ans=0;
dfs(1,1,-1);
for(int i=1;i<=n;++i)
{
ll upo,upe,ta;
if(lev[i]%2)
{
upo=o[1]-o[i]+1;
upe=e[1]-e[i];
}else{
upo=e[1]-o[i]+1;
upe=o[1]-e[i];
}
ta=2*(upo*o[i]%MOD-upe*e[i]%MOD)%MOD*val[i]%MOD;
ta-=val[i];
ta=(ta%MOD+MOD)%MOD;
ans=(ans+ta)%MOD;
}
cout<<ans<<endl;
}
return 0;
}