一、题目链接

　　

 

二、题意

　　给定一棵$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
     
      using namespace std;#define pb(x) push_back(x)#define mk(x, y) make_pair(x, y)typedef long long LL;typedef pair
      
        PII;typedef pair
       
         PLL;const int MAXN = 2e5 + 10;template 
        
          inline void read(T &x) {    int t;    bool flag = false;    while((t = getchar()) != '-' && (t < '0' || t > '9')) ;    if(t == '-') flag = true, t = getchar(); x = t - '0';    while((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0';    if(flag) x = -x;}typedef struct {    int to, next;} Edge;Edge tree[MAXN * 2];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, -1, sizeof(head));    cnt = 0;}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] = 1;    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);    for(int i = 1; i <= N; ++i)read(v[i]);    for(int i = 1; i < N; ++i) {        read(a), read(b);        add(a, b);        add(b, a);    }    dfs0(1, -1);    dp2[1] = dp0[1];    dfs1(1, -1);    LL ans = 0;    for(int i = 1; i <= N; ++i)ans = (ans + dp2[i]) % MOD;    cout << ans << endl;    return 0;}