一、题目链接
http://codeforces.com/contest/960/problem/B
二、题意
给定一棵$N$个节点的树，每个节点的权值$V$。定义树中两点$u_1$和$u_m$的权值和为$A(u_1, u_m) = V_{u_1} - V{u_2} + V{u_3} - V{u_4} + \cdots + (-1)^{m+1}V{u_m}$。求$\sum\limits_{u_i=1}^{N}\sum\limits_{u_j=1}^{N}A(u_i, u_j)\ \%\ (10^9+7)$。
三、思路
显然的树形$dp$。采用"两遍扫描"法。
设$dp1[i]$表示：从$i$出发，在以$i$为根的子树中，可得到的权值和。那么，很容易想到一个式子：预处理$dp1[i]=V[i]$，表示从$i$走到$i$自己的$A$值。然后，对于$i$的所有子节点$j$，有$dp1[i]\ +=\ V[i] - dp1[j]$。在思路中，为表述简洁，我们不考虑取模。如果这样，那就大错特错了。你会发现，连样例2都过不去。画一棵链式树可以发现，其实正确的式子是，$dp1[i] += f[j] * V[i] - dp1[j]$，其中$f[j]$表示以$j$为根节点的子树中节点的个数。为什么要乘以$f[j]$，因为对于以$j$为根的子树中每一个节点$r$，节点$i$都要走一遍去计算$A(i, r)$，所以这个地方要乘以一个$f[j]$。我一开始就是没写，导致一直样例都过不去。
设$dp2[i]$表示：从$i$出发，可得到的权值和(最后累加$dp2[i]$即可)。一遍扫描完成之后，显然有$dp2[1] = dp1[1]$(当然了，要看你的dfs是从哪个节点开始的)。然后，对于$i$的所有子节点$j$，有
\[dp2[j] = 除去以j为根的子树中所有节点的个数*V[j] + dp1[j] - (dp2[i] - 以j为根的子树中所有节点的个数*V[i] + dp1[j])\]
形式化(规范化)表示就是：
\[dp2[j] = (N - f[j]) * V[j] + dp1[j] - (dp2[i] - f[j] * V[i] + dp1[j])\]
即\[dp2[j] = (N - f[j]) * V[j] - (dp2[i] - f[j] * V[i])\]
注意这些"+"、“-”号的意义哦。在第一次扫描中减(实际上是+负的)了的，这里要加(实际上是-正的)回去，就等于没动(没+负也没-正)。同时，第一次加了$f[j] * V[i]$，那么，这一次要减去这个值。
另外，要注意的就是，取模的问题。因为涉及负数和乘法，一次加模数再取模不一定能保证结果为正。所以，要对$dp1[i]$和$dp2[i]$分别做两次取模。
四、代码实现
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
;
template <class T> inline void read(T &x) {
int t;
bool flag = false;
')) ;
';
+ t - ';
if(flag) x = -x;
}
typedef struct {
int to, next;
} Edge;
Edge tree[MAXN * ];
int head[MAXN], cnt;
void add(int from, int to) {
tree[cnt].to = to;
tree[cnt].next = head[from];
head[from] = cnt++;
}
void init() {
memset(head, -, sizeof(head));
cnt = ;
}
LL N, v[MAXN], dp0[MAXN], f0[MAXN], dp2[MAXN];
const LL MOD = 1000000007LL;
void dfs0(int root, int par) {
dp0[root] = v[root], f0[root] = ;
for(int i = head[root]; ~i; i = tree[i].next) {
int to = tree[i].to;
if(to != par) {
dfs0(to, root);
dp0[root] = (f0[to] * v[root] + dp0[root] - dp0[to] + MOD) % MOD;
dp0[root] = (dp0[root] + MOD) % MOD;
f0[root] += f0[to];
}
}
}
void dfs1(int root, int par) {
for(int i = head[root]; ~i; i = tree[i].next) {
int to = tree[i].to;
if(to != par) {
dp2[to] = ((N - f0[to]) * v[to] + dp0[to] - (dp2[root] + dp0[to] - f0[to] * v[root] + MOD) + MOD) % MOD;
dp2[to] = (dp2[to] + MOD) % MOD;
dfs1(to, root);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("inputE.txt", "r", stdin);
#endif // ONLINE_JUDGE
init();
int a, b;
read(N);
; i <= N; ++i)read(v[i]);
; i < N; ++i) {
read(a), read(b);
add(a, b);
add(b, a);
}
dfs0(, -);
dp2[] = dp0[];
dfs1(, -);
LL ans = ;
; i <= N; ++i)ans = (ans + dp2[i]) % MOD;
cout << ans << endl;
;
}