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