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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define int long long
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<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define N 1000010
struct node {
int sze, sum, i;
bool operator < (const node &A) const {
return sum*A.sze < A.sum*sze;
}
};
struct qres {
int u, x, id;
}b[N];
priority_queue<node>q;
int n, m, i, j, k, T;
int f[N], F[N], a[N], dfn[N], tot, L[N], R[N];
int ans[N], x, y;
vector<int>G[N];
struct Binary_tree {
int cnt[N], ans;
void add(int x, int k) {
if(!x) return ;
while(x<=n) cnt[x]+=k, x+=x&-x;
}
int que(int x) {
for(ans=0; x; x-=x&-x) ans+=cnt[x];
return ans;
}
int cha(int x) {
return que(R[x]) - que(L[x]-1);
}
}Bin_size, Bin_sum;
int fa(int x) {
if(F[x] == x) return x;
return F[x] = fa(F[x]);
}
void dfs(int x) {
dfn[x]=++tot; L[x]=tot;
Bin_size.add(dfn[x], 1);
Bin_sum.add(dfn[x], a[x]);
Bin_size.add(dfn[f[x]], -1);
Bin_sum.add(dfn[f[x]], -a[x]);
for(int y : G[x]) dfs(y), debug("%lld %lld\n", x, y);
R[x]=tot;
}
signed main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
n=read(); m=read();
for(i=2; i<=n; ++i) f[i]=read(), G[f[i]].pb(i);
for(i=1; i<=n; ++i) a[i]=read(), F[i]=i;
for(i=2; i<=n; ++i) q.push({1, a[i], i});
dfs(1);
for(i=1; i<=m; ++i) b[i].u=read(), b[i].x=read(), b[i].id=i;
sort(b+1, b+m+1, [] (qres A, qres B) { return A.x < B.x; });
for(i=1; i<=m; ++i) {
auto T = b[i];
while(!q.empty() && q.top().sum + q.top().sze * T.x >=0 ) {
auto t = q.top(); q.pop(); x=t.i;
t.sze=Bin_size.cha(x);
t.sum=Bin_sum.cha(x);
if(fa(x)!=x) continue;
debug(">> (sum)%lld (size)%lld | (x)%lld\n", t.sum, t.sze, x);
F[x]=f[x]; y=fa(x);
Bin_size.add(dfn[f[x]], t.sze);
Bin_size.add(dfn[f[y]], -t.sze);
Bin_sum.add(dfn[f[x]], t.sum);
Bin_sum.add(dfn[f[y]], -t.sum);
if(y == 1) continue;
int s1 = Bin_size.cha(y), s2 = Bin_sum.cha(y);
q.push({s1, s2, y});
}
int s1 = Bin_size.cha(T.u), s2 = Bin_sum.cha(T.u);
ans[T.id] = s1 * T.x + s2;
debug("Ans for %lld(u : %lld) is %lld [%lld %lld]\n", T.x, T.u, ans[T.id], s1, s2);
}
for(i=1; i<=m; ++i) printf("%lld\n", ans[i]);
return 0;
}
|
