比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAATTTTTT
题目名称 Asm.Def的基本算法 最终得分 40
用户昵称 sxysxy 运行时间 6.018 s
代码语言 C++ 内存使用 0.97 MiB
提交时间 2015-11-02 10:09:18
显示代码纯文本
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <string>
#define AC_MOD (1000000007)
using namespace std;
struct node
{
	int pr;
	int value;
//	int chd;	
};

node ns[100001];
long long res = 0;

int lca(int a,int b)
{                    
	int p1 = a,p2 = b;
	vector<int> l1,l2;
	
	if(a == b)return a;
	if(a == 1 || b == 1)return 1;
	
	//创建p1,p2的祖先链 
	while(p1 != 1)
	{
		if(p1 == p2)return p2;
		l1.push_back(p1);
		p1 = ns[p1].pr; 
	}
	p1 = a;
	while(p2 != 1)
	{
		if(p1 == p2)return p1;
		l2.push_back(p2);
		p2 = ns[p2].pr;
	}
	
	//如果p1,p2互相都不是对方的祖先,则在祖先链中找公共的。。
	for(p1 = 0; p1 < l1.size(); p1++)
	{
		for(p2 = 0; p2 < l2.size(); p2++)
		{
			if(l1[p1] == l2[p2])
				return l1[p1];
		}
	} 
	return 1;
}

int main()
{
	freopen("asm_algo.in", "r", stdin);
	freopen("asm_algo.out", "w", stdout);
	int n,a,b;
	scanf("%d %d", &n, &b);
	ns[1].value = b;
	for(int i = 2; i <= n; i++)
	{
		scanf("%d %d", &a, &b);
		ns[i].pr = a;
		ns[i].value = b;
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			res += (ns[i].value * ns[j].value * ns[lca(i,j)].value)%AC_MOD;
			res %= AC_MOD;
		}
	}	
	cout << res << endl;
	return 0;
}