比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
AWWWWWTTTT |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
10 |
用户昵称 |
pppoooiiizzy |
运行时间 |
4.174 s |
代码语言 |
C++ |
内存使用 |
0.33 MiB |
提交时间 |
2015-11-02 10:38:29 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<sstream>
#include<functional>
#include<set>
const int maxn = 1000 + 100;
using namespace std;
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define drep(i, j, k) for(int i = j; i >= k; i--)
#define INF 03xfffffff
#define MOD 1000000007
#define LL unsigned long long
struct node {
int father, w, deep;
bool root, vis;
}tree[maxn];
int m, n, i, j, k, Ar, Sa, w, temp;
bool flag;
LL sum = 0;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while( ch < '0' || ch > '9') {if( ch == '-') f = -1; ch = getchar();}
while( ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
void hehe(){cout<<++temp<<endl;}
void init()
{
n = read(); tree[1].w = read();
tree[1].root = true;
rep(i, 2, n) {
tree[i].father = read(), tree[i].w = read();
}
}
void dfs(int x, int dept)
{
if(tree[x].vis) return;
tree[x].deep = dept, tree[x].vis = 1;
for(int i = 1; i <= n; i++) {
if(tree[i].father == x) dfs(i, dept++);
}
}
int LCA(int Ar, int Sa)
{
if( Ar == 1 || Sa == 1) return tree[1].w;
if( Ar == Sa) return tree[Ar].w;
if( tree[Ar].father == tree[Sa].father) return tree[tree[Ar].father].w;
while( tree[Ar].deep != tree[Sa].deep) {
if( tree[Ar].deep < tree[Sa].deep)
Sa = tree[Sa].father;
else Ar = tree[Ar].father;
}
while( tree[Ar].father != tree[Sa].father) {
Ar = tree[Ar].father;
Sa = tree[Sa].father;
}
return tree[tree[Ar].father].w;
}
int main()
{
freopen("asm_algo.in", "r", stdin);
freopen("asm_algo.out", "w", stdout);
init();
dfs(1, 1);
rep(i, 1, n)
rep(j, 1, n) {
//cout<<tree[i].w<<" "<<tree[j].w<<" "<<LCA(i, j)<<endl;
sum += tree[i].w % MOD * tree[j].w % MOD * LCA(i, j) % MOD;
}
cout<<sum<<endl;
}