比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
AAAAAAATTT |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
70 |
用户昵称 |
皓芷 |
运行时间 |
3.540 s |
代码语言 |
C++ |
内存使用 |
3.36 MiB |
提交时间 |
2018-11-07 14:06:20 |
显示代码纯文本
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100001;
const long long mod=1000000007;
int n,fa[maxn],v,head[maxn],next[maxn<<1],to[maxn<<1],cnt=0;
long long w[maxn],ans=0ll;
vector<int>g;
void addedge(int u,int v)
{
next[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
int find(int u)
{
return fa[u]==u?u:fa[u]=find(fa[u]);
}
int dfs(int u,int f)
{
for(int i=head[u];i;i=next[i])
dfs(to[i],u);
g.push_back(u);
for(int i=0;i<g.size();++i)
{
long long now=((w[u]*w[g[i]])%mod)*w[find(g[i])]%mod;
if(u!=g[i])now=(now<<1)%mod;
ans=(now+ans)%mod;
}
fa[u]=f;
}
int main()
{
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
scanf("%d%lld",&n,&w[1]);
fa[1]=1;
for(int i=2;i<=n;++i)
{
fa[i]=i;
scanf("%d%lld",&v,&w[i]);
addedge(v,i);
}
dfs(1,1);
printf("%lld",ans);
return 0;
}