比赛 “Asm.Def战记之太平洋”杯 评测结果 AWWWWWTTTT
题目名称 Asm.Def的基本算法 最终得分 10
用户昵称 VG|Kn. 运行时间 4.364 s
代码语言 C++ 内存使用 1.46 MiB
提交时间 2015-11-02 11:16:14
显示代码纯文本
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int maxn = 100000 + 100;
int n;
long long ans = 0;

struct node
{
	int p;
	int w;
	int d;
}t[maxn];

int lca(int x, int y)
{
	int out;
	if (t[x].d < t[y].d)
	{
		y = t[y].p;
		lca(x, y);
	}
	if (t[x].d > t[y].d)
	{
		x = t[x].p;
		lca(x, y);
	}
	if (t[x].d == t[y].d)
	{
		if (x == y)
		{
			out = x;
		}
		else
		{
			if (t[x].p == t[y].p)
			{
				out = t[x].p;
			}
			else
			{
				x = t[x].p;
				y = t[y].p;
				lca(x, y);
			}
		}
	}
	return out;
}

int main()
{
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	t[1].d = 1;
	t[1].p = 0;
	cin >> n >> t[1].w;
	for (int i = 2; i <= n; i++)
	{
		cin >> t[i].p >> t[i].w;
		t[i].d = t[t[i].p].d + 1;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			ans += t[i].w * t[j].w * t[lca(i, j)].w;
		}
	}
	cout << ans % 1000000007;
	return 0;
 }