首页 > 代码库 > 统计损失
统计损失
题目描述
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国将受到的损失之和。
样例输入
5
7 6 6 1 1
1 2
2 3
2 4
1 5
样例输出
778
提示
【数据规模和约定】
n<=100;
n<=3000;
n<=100000
题意
给你一棵树，求树上任意一条路径的节点的积的和。
题解
（1）头尾的lca等于头或尾
f[i]=∑f[v[i]]∗a[i],f[i]表示以i节点为头（尾）的路径的乘积之和
（2）头尾的lca不为头或尾，即倒“V”型
我们发现若两点（u,v）的lca为i ，那么可以划分为u到i的直线*v到i的直线。
那么lca为i的路径乘积之和为
对于搜到的每一个子节点，ans:=ans+sum*f[v];sum:=sum+f[v]*a[u];
const oo=10086;maxn=200010;var n,i,u,v,tot,ans:longint; a,vet,next,head,f:array[0..maxn] of longint;procedure add(u,v:longint);begin inc(tot); vet[tot]:=v; next[tot]:=head[u]; head[u]:=tot; inc(tot); vet[tot]:=u; next[tot]:=head[v]; head[v]:=tot;end;procedure dfs(u,pre:longint);var e,v:longint;begin e:=head[u]; while e<>0 do begin v:=vet[e]; if v<>pre then begin dfs(v,u); ans:=(ans+(f[u]-a[u]+oo)*f[v]) mod oo; f[u]:=(f[u]+f[v]*a[u]) mod oo; end; e:=next[e]; end; ans:=(ans+f[u]) mod oo;end;beginread(n);for i:=1 to n dobegin read(a[i]); f[i]:=a[i];end;for i:=1 to n-1 dobegin read(u,v); add(u,v);end;dfs(1,0);write(ans);end.
统计损失
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。