题目大意

给定一棵无向树所有节点的权值。求其所有路径权值积的和，答案对10086取模。

数据范围

节点数\(n\)，\(n \leq 100000\)

分析

题意即统计所有的路径权值积的和。

朴素算法

枚举每条路径的起点和终点，再求出每条路径的权值积，求和取模即可。复杂度\(O(n^2)\)

对于\(n \leq 100000\)的数据范围，显然是会TLE的。

算法2

树形DP ,统计每个点的子树到当前点的路径积的和，再DFS 逆序计算并合并答案即可，时间复杂度\(O(n)\)。合并时需注意合并一次的效率，要保证能够依倒〇(子树个数)合并，并且需要注意\(10086\)不能求逆元。

参考代码

#include 
    
     using namespace std;#define rg registerconst int MAXN = 100000 + 5;const int MOD = 10086;int n, C[MAXN], F[MAXN];int H[MAXN], cntE;int ans;struct Edge{    int to, next;}E[MAXN * 2];inline void AddEdge(int u, int v){    E[++cntE] = (Edge){v, H[u]};    H[u] = cntE;    return ;}void Input(){    scanf("%d", &n);    for(rg int i = 1; i <= n; ++i)        scanf("%d", &C[i]);    for(rg int i = 1, u, v; i < n; ++i)    {        scanf("%d%d", &u, &v);        AddEdge(u, v);        AddEdge(v, u);    }    return ;}void Tree_Dp(int cur, int fa)   {    for(rg int i = H[cur]; i; i = E[i].next)    {        int& ne = E[i].to;        if(ne == fa)            continue;        Tree_Dp(ne, cur);        (ans += F[ne] * F[cur]) %= MOD;        (F[cur] += C[cur] * F[ne]) %= MOD;    }    (F[cur] += C[cur]) %= MOD;    (ans += F[cur]) %= MOD;    return ;}int main(){    Input();    Tree_Dp(1, 0);    printf("%d\n", ans);    return 0;}