Submission #278822

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <iterator>
#include <complex>
#include <valarray>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <limits>

using namespace std;

//#define DEBUG 1


#if defined(DEBUG)
#define dump(i) dumper(#i":",i)
#define dump2(i,j) writeln(#i":"+str(i)+" "#j":"+str(j))
#else
#define dump(i) 0
#define dump2(i,j) 0
#endif
#if defined(DEBUG)
#define debug(i) i
#define stop readln()
#else
#define debug(i) 0
#define stop 0
#endif
#define INT_MAX numeric_limits<int>::max()
#define LL_MAX numeric_limits<llong>::max()
#define ALL(g) (g).begin(),(g).end()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define rrepx(i, x, n) for(int i = (n - 1); i >=(x); i--)
#define rrep(i, n) rrepx (i,0,n)
#define repx(i, x, n) for(int i = (x); i < (n); i++)
#define rep(i, n) repx(i,0,n)
#define INF INT_MAX
#define type_sp template<>
#define type(T) template<class T>
#define type2(T, F) template<class T, class F>
#define type3(T, F, G) template<class T, class F, class G>
#define pb push_back
#define mp make_pair
#define pqueue priority_queue
#define vec vector
#define mset(m, v) memset(m, v, sizeof(m))
#define SAFED_SCOPE(i, v) for(int _____SCOPE##i = 0; _____SCOPE##i == 0;)for(aut(i, v); _____SCOPE##i == 0; _____SCOPE##i++)
#define each(i, v) SAFED_SCOPE(_____EACH##i, v) for(aut(i, _____EACH##i.begin()); i != _____EACH##i.end(); i++)
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r, v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif

typedef long long llong;
typedef unsigned int uint;
typedef unsigned long long ullong;
typedef vector<int> vi;
typedef vector<llong> vl;
typedef vector<double> vd;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<llong,llong> pll;
typedef pair<double,double> pdd;
typedef pair<string,string> pss;
typedef vector<vi> mati;
typedef vector<vl> matl;
typedef vector<vd> matd;
typedef vector<vs> mats;
typedef map<int,int>mii;
typedef map<int,vi> mivi;
typedef map<int,pii>mipi;
typedef map< int,vec<pii> > mivpi;


type(T) inline vector< vector<T> > matrix(int l,int c,T init){vector< vector<T> >v;rep(i,l){vector<T> s;s.assign(c,init);v.pb(s);}return v;}
type(T) inline T gcd(T a,T b){while(b){T t=a%b;a=b;b=t;}return a;}
vs inline split(string haystack,string needle=" "){vs v;string::size_type index=0,index2=0;while((index2=haystack.find(needle,index))!=string::npos){ v.pb(haystack.substr(index,index2-index));index=index2+needle.length();}v.pb(haystack.substr(index,haystack.length()-index));return v;}
type(T) inline T parce(string s) {T v; istringstream stin(s);stin>>v;return v;}
type(T) inline string str(T v){ostringstream stout;stout<<v;return stout.str();}
string inline readln(){string v;getline(cin,v);return v;}
type(T) inline T read(){T v;cin>>v;return v;}
type(T) inline T readln_as(){T v;cin>>v;readln();return v;}
type(T) inline vector<T> readln_parce(){vector<T> v;vs s=split(readln()," ");each(i,s){v.pb(parce<T>(*i));}return v;}
type(T) inline vector<T> readln_parce(int n){vector<T> v;T t;rep(i,n){cin>>t;v.pb(t);}readln();return v;}
type(T) inline vector<T> readlns_as(int n){vector<T> v;rep(i,n){v.pb(readln_as<T>());}return v;}
inline int ri(){return read<int>();}
inline llong rl(){return read<llong>();}
inline string rs(){return read<string>();}
inline int rli(){return readln_as<int>();}
inline void nl(){readln();}
inline void writedbl(double v){string ss="";printf("%-lf",v);}
inline void writedbl(double v,int k){string ss="";printf((ss+"%-."+str(k)+"lf").c_str(),v);}
type(T) inline void write(T v){cout << v;}
type_sp inline void write(double v){writedbl(v);}
inline void writeln(){cout << endl;}
type(T) inline void writeln(T v){write(v);writeln();}
type(T) inline T dumper(string s,T v){writeln(s+str(v));return v;}
type2(T,S) inline void mvadd(map< T, vec<S> > &m,T t,S s){if(m.find(t)!=m.end()){m[t].pb(s);}else{vec<S> v;v.pb(s);m[t]=v;}}


type(T) struct segtree{
private:
	vector<T> nodes;
	int leafs;
	T zero;
	T notyet;

public:
	segtree(vector<T> a,T zero=0,T notyet=-1):zero(zero),notyet(notyet){
		int n=a.size();
		int c=0;
		int d=1;
		while(n>d)d*=2;;
		nodes.assign(d,notyet);
		nodes.insert(nodes.end(),ALL(a));
		rep(i,d-n){nodes.pb(zero);}
		leafs=d;

	};


	inline void change(int place,int value){
		int c=leafs+place-1;

		nodes[c]+=value;

		while(nodes[c/2]!=notyet){
			nodes[c/2]=notyet;
			c=c/2;
		}

	};

	inline T query(int b,int e){
		return _query(b,e+1,1,1,leafs+1);
	};

private:

	inline  T op(T a,T b){

	}

	inline int node(int index){
		if(nodes[index]==notyet){
			nodes[index]=op(node(2*index),node(2*index+1));
		}
		return nodes[index];
	}


	T _query(int qlc,int qro,int k,int lc,int ro){
		if(qro<=lc || ro<=qlc)return zero;
		else if(qlc<=lc && ro<=qro)return node(k);
		else return op(_query(qlc,qro,2*k,lc,(lc+ro)/2),_query(qlc,qro,2*k+1,(lc+ro)/2,ro));
	}

};

//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
vector< vector<pii> > node;
vector<pii> memo;

pii solve(int start){
	int m=INF;
	int nex=-1;
	if(!(memo[start].first==-1 && memo[start].second==-1))return memo[start];
	if(node[start].empty()){
		memo[start]=mp(-1,0);
		return mp(-1,0);
	}
	each(i,node[start]){
		if(!(i->second==INF)){
			pii w=solve(i->first);
			if(!(w.second==INF)){
				if(m>(w.second+i->second)){
					m=w.second+i->second;
					nex=i->first;
				}			
			}
		}
	}
	pii d=mp(nex,m);
	memo[start]=d;
	return d;
}


void mymain(void){
	int n=ri(),q=ri();nl();

	vi par;
	par.assign(n,-1);
	node.assign(n,vector<pii>());
	memo.assign(n,mp(-1,-1));
	repx(i,1,n){
		int p=ri(),w=ri();nl();
		par[i]=p-1;
		node[p-1].pb(mp(i,w));
	}
	rep(i,n){
		sort(ALL(node[i]));
	}

	rep(i,q){
		int x=rli()-1;
		aut(ex,lower_bound(ALL(node[par[x]]),mp(x,-1)));
		ex->second=INF;
		while(x>=0){
			if(memo[par[x]].first==x){
				memo[par[x]]=mp(-1,-1);
				x=par[x];
			}else{
				break;
			}
		}
		pii w=solve(0);
		if(w.second==INF)writeln(-1);
		else writeln(w.second);
	}



end:;
	stop;
}



int main(void){

	mymain();
	return 0;

}


//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Submission Info

Judge Result