题意描述

SJY有一天被LLT紧急召去计算一些可能的损失。

LLT元首管理的SHB国的交通形成了一棵树，现在将会出现一颗陨石砸在SHB国中，并且陨石砸毁的必定是SHB国构成的交通树上的一条路径。

SHB国的损失可表示为被砸毁的路径上的所有城市价值之积。

现在还暂时无法确定陨石的掉落路线，所以LLT元首希望SJY能够告诉他SHB国在受到每一种砸毁方式后会受到的损失之和模$10086$之后的值。

注意：单独的一个节点也被认为是合法的路径。

输入格式

第$1$行包含一个数$n$，表示城市数。

第$2$行包含$n$个数，第$i$个数表示第$i$个城市的价值。

第$3$行到$n+1$行，每行两个数$u,v$，表示城市$u,v$之间有一条道路。

输出格式

输出仅有一行，包含一个数，表示SHB国将受到的损失之和。

Input & Output ‘s examples

Input ‘s eg

5
7 6 6 1 1 
1 2
2 3
2 4
1 5

Output ‘s eg

778

数据范围与约定

对于$20\%$的数据，保证$0 \leq n \leq 100$;

对于$50\%$的数据，保证$0 \leq n \leq 3000$;

对于$100\%$的数据，保证$0 \leq n \leq 10^4$。

分析

题目中的题意并不明确，需要先理清题意。

题意即求出一颗树上所有路径的价值之和。路径的价值定义为路径经过的点的乘积。

考虑树形dp，设$f[i]$表示以$i$为根的子树的答案，转移时从下向上转移。

不难发现，每一条路径的状态有两种，分别是直链与折链。

若路径为一条直链，则$f[u] = \sum f[to] * val[u]$，最后的答案为$\sum_{i = 1}^n f[i]$。

若路径为一条折链，则相当于是两条直链，需要分开处理。

假设处理到了$u$的子树$v$，则让$to$这颗子树负责其中一条直链，另一条让其他子树负责，即$\sum f[to] * f[son[u]]$，$(son[u] \neq to)$。

但要注意，由于我们将折链拆成了两条直链，计算时需要使用到$f$数组的元素，因此对于折链的计算是不能加入$f$数组的。直接加入答案即可。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 100010

using namespace std;

const int HA = 10086;
int n , a[N];

struct Edge{
    int from , to;
    int last;
}edge[N << 1];

int edge_num;
int head[N << 1];

I void add_edge(int from , int to){
    edge[++ edge_num] = (Edge){from , to , head[from]};
    head[from] = edge_num;
}

ll ans , f[N];

void search(int u , int fa){
    ll sum = 0;
    f[u] = a[u];    //由于单独的一个点也是合法路径，所以我们需要加上单独一个点的答案
    for(int i = head[u]; i ; i = edge[i].last){
        int to = edge[i].to;
        if(to == fa) continue;
        search(to , u);
        f[u] += f[to] * a[u] , f[u] %= HA; //计算直链的答案
        ans += sum * f[to] , ans %= HA; //单独加入折链的答案。
        sum += f[to] * a[u] , sum %= HA; 
        //重新计算折链的贡献，这一句必须放于上句之后，因为必定会有一条直链。
    }
    ans += f[u] , ans %= HA;    //最后加入直链的答案
}

int main(){
    int u , v;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 1; i <= n - 1; i ++){
        cin >> u >> v;
        add_edge(u , v);
        add_edge(v , u); 
    }
    search(1 , 0);
    cout << ans % HA << "\n";
    return 0;
}

THE END