比赛 “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;
}