2084. Asm.Def的基本算法
★☆ 输入文件：asm_algo.in 输出文件：asm_algo.out 简单对比时间限制：1 s 内存限制：256 MB
【题目描述】
“有句美国俗语说，如果走起来像鸭子，叫起来像鸭子，那就是一只鸭子。”斯科特·华莱士看着Asm.Def面前屏幕上滚动的绿色字符，若有所思地说。
“什么意思？”
“你的数据。看上去是一棵树。”
“按照保密条令，我什么也不说这是最好的——但见你这么热情，一句话不说也不好。”Asm.Def停下手中的快速数论变换，“确实是树。”
“然后你怎么算出来目标的位置？”
“都需要按照基本算法，按照图论的那一套理论，去产生。听说过LCA吗？不是那个印度飞机，我是说最近公共祖先……”
Asm.Def通过分析无线电信号得到了一棵有n个节点，以1为根的树。除1之外，节点i的父亲是p_i。节点带有权值，节点i的权值是w_i。
我们定义某点的祖先为从根到它路径上的所有点（包括它本身），而两个节点a、b的最近公共祖先是某个点p，使得p同时是a、b的祖先，而且p离根最远。
Asm.Def想要求出
（文字：∑∑w_i*w_j*w_LCA(i,j)），
其中LCA(i,j)是i、j的最近公共祖先，他认为这个值至关重要。由于这个值可能很大，Asm.Def只需要知道它模1,000,000,007（即10^9+7）的结果。
【输入格式】
第1行两个整数：n和w_1.
第2行到第n行，第i行有两个整数p_i和w_i。
【输出格式】
一行一个整数，即答案模1,000,000,007的值。
【样例输入】
2 21 1
【样例输出】
17
【提示】
1×1×1+1×2×2+2×1×2+2×2×2=17。
对于30%的数据，n<=100，w_i<=10。
对于60%的数据，n<=1000，w_i<=1000.
对于100%的数据，1<=n<=10^5，0<=w_i<=10^9，1<=p_i<i.
思路：
这个题的答题思路跟上一个题差不多，如果有不知道思路的请转：
但是我们又发现这个题是求也就是说差不多要求两遍上一个题，为什么？！
我们来手模一下样例：（1,1）（1,2）（2,1）（2,2）我们从上一个题得知我们是在后面求的像（1,1）（2，2）这样的问题，所以这种情况我们可以后面单独做。我们在看（1,2,）和（2,1）这两种情况是完全一样的、、也就是说我们可以算是求了两遍上一个题的（2,1）我们dfs完以后再乘以2就解决问题了、、
还有我们在dfs中要算的东西多了一个w[i]*w[j]这样我们怎么来解决这个问题呢？！我们只需要把它的sum初值附成w[i]就好了，这样我们可以在进行相乘的时候把每一个点的sum都乘入、、、
代码：
#include#include #include #include #include #define N 200010#define mod 1000000007#define ll long long using namespace std;ll n,y,tot,w[N],dad[N],sum[N],head[N],ans;struct Edge{ ll to,from,next;}edge[N];ll add(ll x,ll y){ tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot;}ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}ll dfs(ll x){ sum[x]=w[x]; for(int i=head[x];i;i=edge[i].next) { ll t=edge[i].to; if(!dad[t]) { dad[t]=x;dfs(t); ans=(ans%mod+sum[x]%mod*sum[t]%mod*w[x]%mod)%mod; sum[x]=(sum[x]%mod+sum[t]%mod)%mod; } }}int main(){ freopen("asm_algo.in","r",stdin); freopen("asm_algo.out","w",stdout); n=read();w[1]=read(); for(ll i=2;i<=n;i++) { y=read(),w[i]=read(); add(y,i); } dfs(1);ans=ans%mod*2%mod; for(ll i=1;i<=n;i++) ans=(ans%mod+w[i]%mod*w[i]%mod*w[i]%mod)%mod; printf("%lld",ans); return 0;}