记录编号	261343	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2016] 烟花表演	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	3.414 s
提交时间	2016-05-16 22:45:05	内存使用	23.20 MiB

/*
Peoblem:Fireworks;
Language:c++;
by dydxh;
2016.05.16;
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<ctime>
#include<cstdlib>
#define ll long long
using namespace std;
const int maxn=300005;
const int oo=2000000000;
int n,m,cnt,N;
vector<int> son[maxn];
ll length[maxn];
struct Heaper{
    int l,r,h;
    ll val;
    Heaper(){}
    Heaper(ll _val) : l(0),r(0),h(0),val(_val) {}
}H[maxn<<1];
int root[maxn];
inline int read(){
    int x=0;bool flag=false;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
inline void swap(int &x,int &y){int t=x;x=y,y=t;}
int merge(int x,int y){
    if(x==0 || y==0) return x+y;
    if(H[x].val<H[y].val) swap(x,y);
    H[x].r=merge(H[x].r,y);
    if(H[H[x].l].h<H[H[x].r].h) swap(H[x].l,H[x].r);
    H[x].h=H[H[x].r].h+1;
    return x;
}
void Build_Function(){
    for(int i=n;i>=1;i--){
        for(vector<int>::iterator it=son[i].begin();it!=son[i].end();it++){
            if(*it>n){
                H[++cnt]=Heaper(length[*it]);
                H[++cnt]=Heaper(length[*it]);
                root[*it]=merge(cnt,cnt-1);
                root[i]=merge(root[i],root[*it]);
                continue;
            }
            for(int j=1;j<son[*it].size();j++)
                root[*it]=merge(H[root[*it]].l,H[root[*it]].r);
            ll r=H[root[*it]].val;root[*it]=merge(H[root[*it]].l,H[root[*it]].r);
            ll l=H[root[*it]].val;root[*it]=merge(H[root[*it]].l,H[root[*it]].r);
            H[++cnt]=Heaper(l+length[*it]);
            root[*it]=merge(root[*it],cnt);
            H[++cnt]=Heaper(r+length[*it]);
            root[*it]=merge(root[*it],cnt);
            root[i]=merge(root[i],root[*it]);
        }
    }
}
int head,tail;
ll pointer[maxn<<1];
void Get_Point(){
    head=0,tail=1,pointer[1]=root[1];
    while(head<tail){
        int tn=pointer[++head];
        if(H[tn].l) pointer[++tail]=H[tn].l;
        if(H[tn].r) pointer[++tail]=H[tn].r;
    }
    pointer[0]=tail;
    for(int i=1;i<=tail;i++) pointer[i]=H[pointer[i]].val;
    sort(pointer+1,pointer+1+tail);
}
int main(){
    freopen("fireworks.in","r",stdin);
	freopen("fireworks.out","w",stdout);
    n=read(),m=read(),N=n+m;
    for(int i=2;i<=n;i++){
        int father=read();length[i]=read();
        son[father].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int father=read();length[i+n]=read();
        son[father].push_back(i+n);
    }
    Build_Function();
    Get_Point();
    ll k=son[1].size()-pointer[0],b=0;
    for(int i=1;i<=N;i++) b+=length[i];
    for(int i=1;i<=pointer[0];i++){
        k++,b-=pointer[i];
        if(k!=0) continue;
        printf("%lld\n",b);
        break;
    }
    return 0;
}