1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
int w[2000010]={0},st[10010],child[2000010][2],n,m;
int dfs(int a){
if(a>=n) return w[a];
w[a]=dfs(child[a][0])+dfs(child[a][1]);
return w[a];
}
int findBox(int stw,int a){
if(a>=n){
return a;
}
if(w[child[a][0]]<=w[child[a][1]]){
w[child[a][0]]+=stw;
return findBox(stw,child[a][0]);
}
w[child[a][1]]+=stw;
return findBox(stw,child[a][1]);
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[n+i];
for(int i=0;i<m;i++) cin>>st[i];
for(int i=1;i<n;i++){
int p,s,t;cin>>p>>s>>t;
child[p][0]=s;child[p][1]=t;
}
int root=1;
w[1]=dfs(root);
for(int i=0;i<m;i++){
cout<<findBox(st[i],root)<<" ";
}
return 0;
}
|