比赛 “Asm.Def战记之太平洋”杯 评测结果 AWWWWWTTTT
题目名称 Asm.Def的基本算法 最终得分 10
用户昵称 asddddd 运行时间 4.898 s
代码语言 C++ 内存使用 8.21 MiB
提交时间 2015-11-02 11:44:51
显示代码纯文本
//
//  main.cpp
//  asm_alog
//
//  Created by Qing Liu on 15/11/2.
//  Copyright © 2015年 Qing Liu. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define mod 1000000007
#define maxn 110000
using namespace std;
typedef unsigned long long ll;
vector<int>G[maxn];
void addedge(int from,int to){
    G[from].push_back(to);
}
ll ans=0;
int depth[maxn*4],vs[4*maxn],id[maxn],seg[maxn*8],k=0,c[maxn];
void LCA(int v,int d){
    depth[v]=d;
    id[v]=k;
    vs[k++]=v;
    for (int i=0; i<G[v].size(); i++) {
        int temp=G[v][i];
            LCA(temp, d+1);
            vs[k]=v;
            depth[k++]=d;
    }
}
int build(int l,int r,int c){
    if (l==r) {
        return seg[c]=vs[l];
    }
    int mid=(l+r)/2;
    int a=build(l, mid, c<<1);
    int b=build(mid+1, r, c<<1|1);
    return seg[c]=depth[id[a]]<depth[id[b]]?a:b;
}
int searrch(int l,int r,int la,int ra,int c){
    if (l>=la&&r<=ra) {
        return seg[c];
    }
    int mid=(l+r)/2;
    if (ra<=mid) {
        return searrch(l,mid,la,ra,c<<1);
    }
    if (la>mid) {
        return searrch(mid+1, r, la, ra, c<<1|1);
    }
    int ta=searrch(l,mid,la,ra,c<<1);
    int tb=searrch(mid+1, r, la, ra, c<<1|1);
    return depth[id[ta]]<depth[id[tb]]?ta:tb;
}
int LCAS(int l,int r){
    l=id[l];
    r=id[r];
    if (l>r) {
        int temp=l;
        l=r;
        r=temp;
    }
    return searrch(0, k-1, l, r, 1);
}
int main() {
    freopen("asm_algo.in", "r", stdin);
    freopen("asm_algo.out", "w", stdout);
    ios::sync_with_stdio(0);
    int n,temp;
    cin>>n>>temp;
    c[1]=temp;
    for (int i=2; i<=n; i++) {
        int p;
        cin>>p>>temp;
        addedge(p, i);
        c[i]=temp;
    }
    LCA(1, 1);
    build(0, k-1, 1);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            ll asd=1;
            asd*=c[i];
            asd*=c[j];
            asd%=mod;
            asd*=c[LCAS(i, j)];
            asd%=mod;
            ans+=asd;
            ans%=mod;
        }
    }
    cout<<ans;
    return 0;
}