题意描述

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