比赛 |
2024暑假C班集训B |
评测结果 |
AAAAAAAAWW |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
80 |
用户昵称 |
wzh0425 |
运行时间 |
0.106 s |
代码语言 |
C++ |
内存使用 |
4.09 MiB |
提交时间 |
2024-07-11 10:40:27 |
显示代码纯文本
- #include<bits/stdc++.h>
- using namespace std;
- long long n,w[100005],hd[200005],nxt[200005],ver[200005],idx,s[100005],res;
- void add(long long x,long long y){
- ver[++idx]=y;
- nxt[idx]=hd[x];
- hd[x]=idx;
- }
- long long dfs(long long x){
- long long sum=0;
- for (long long i=hd[x];i;i=nxt[i]){
- long long y=ver[i];
- sum+=dfs(y);
- }
- s[x]=sum+w[x];
- return s[x];
- }
- long long mul(long long x,long long y){
- return x*y%1000000007;
- }
- void getRes(long long p){
- long long sz=s[p];
- res+=mul(mul(w[p],w[p]),sz*2-w[p]);
- for (long long i=hd[p];i;i=nxt[i]){
- res+=mul(mul(s[ver[i]],sz-s[ver[i]]-w[p]),w[p]);
- getRes(ver[i]);
- }
- return;
- }
- int main(){
- freopen("asm_algo.in","r",stdin);
- freopen("asm_algo.out","w",stdout);
- scanf("%d%d",&n,&w[1]);
- for (long long i=2;i<=n;i++){
- long long x;
- scanf("%d%d",&x,&w[i]);
- add(x,i);
- }
- dfs(1);
- getRes(1);
- cout<<res%1000000007;
- return 0;
- }