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
|
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <queue>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ri register int
#define ll long long
#define ull unsigned long long
#define SIZE 1<<22
using std::min;
using std::max;
using std::priority_queue;
using std::queue;
using std::vector;
using std::pair;
using namespace __gnu_pbds;
inline char gc(){
static char buf[SIZE],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=100005;
const int inf=0x7fffffff;
int LIM;
int n;
vector <int> son[maxn];
int fa[maxn][33],mi[maxn][33];
ll f[maxn][33],k;
int pos[35],tot=0,cnt=0,ms=inf;
ll ans=0;
int main(){
int x,y;
freopen("wtf.out","w",stdout);
freopen("graph4.in","r",stdin);
read(n),read(k);
LIM=log2(k)+1;
for(ri i=1;i<=n;i++){
read(x),x++;
fa[i][0]=x,son[x].push_back(i);
}
for(ri i=1;i<=n;i++)read(f[i][0]),mi[i][0]=f[i][0];
for(ri o=1;o<=LIM;o++){
for(ri i=1;i<=n;i++){
fa[i][o]=fa[fa[i][o-1]][o-1];
f[i][o]=f[i][o-1]+f[fa[i][o-1]][o-1];
mi[i][o]=min(mi[i][o-1],mi[fa[i][o-1]][o-1]);
}
}
while(k){
if(k%2)pos[++tot]=cnt;
k=k>>1;
cnt++;
}
for(ri i=1;i<=n;i++){
ms=inf,ans=0,x=i;
for(ri j=1;j<=tot;j++){
ans+=f[x][pos[j]];
ms=min(ms,mi[x][pos[j]]);
x=fa[x][pos[j]];
}
printf("%lld %d\n",ans,ms);
}
return 0;
}
|