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; }
|