Problem:
 Score : 400 points    Problem Statement Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N . Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N : P_1, P_2, \cdots, P_N .  Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):   In one move, if the piece is now on Square i  (1 \leq i \leq N) , move it to Square P_i . Here, his score increases by C_{P_i} .   Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)      Constraints  2 \leq N \leq 5000  1 \leq K \leq 10^9  1 \leq P_i \leq N  P_i \neq i  P_1, P_2, \cdots, P_N are all different.  -10^9 \leq C_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_1  P_2  \cdots  P_N  C_1  C_2  \cdots  C_N       Output Print the maximum possible score at the end of the game.        Sample Input 1 5 2
2 4 5 1 3
3 4 -10 -8 8      Sample Output 1 8  When we start at some square of our choice and make at most two moves, we have the following options:   If we start at Square 1 , making one move sends the piece to Square 2 , after which the score is 4 . Making another move sends the piece to Square 4 , after which the score is 4 + (-8) = -4 .  If we start at Square 2 , making one move sends the piece to Square 4 , after which the score is -8 . Making another move sends the piece to Square 1 , after which the score is -8 + 3 = -5 .  If we start at Square 3 , making one move sends the piece to Square 5 , after which the score is 8 . Making another move sends the piece to Square 3 , after which the score is 8 + (-10) = -2 .  If we start at Square 4 , making one move sends the piece to Square 1 , after which the score is 3 . Making another move sends the piece to Square 2 , after which the score is 3 + 4 = 7 .  If we start at Square 5 , making one move sends the piece to Square 3 , after which the score is -10 . Making another move sends the piece to Square 5 , after which the score is -10 + 8 = -2 .   The maximum score achieved is 8 .       Sample Input 2 2 3
2 1
10 -7      Sample Output 2 13       Sample Input 3 3 3
3 1 2
-1000 -2000 -3000      Sample Output 3 -1000  We have to make at least one move.       Sample Input 4 10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719      Sample Output 4 29507023469  The absolute value of the answer may be enormous.

Solution (Python):

import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                
                score1 = loop_score * (q - 1) + MAX
                
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, MAX)
                break
            else:
                
                score = MAX
                break
        else:
            next = p[next]
    else:
        score = MAX

    ans = max(ans, score)


print(int(ans))

Solution (Python):
N, K = map(int, input().split())
P = [int(i)-1 for i in input().split()]
C = [int(i) for i in input().split()]


ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-i-1)//l
            now += tot*e
        ans = max(ans, now)
print(ans)

Solution (Python):
import numpy as np
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
cycles, check = [], [False]*n
for pi in p:
    if not check[pi-1]:
        curr, cycle = pi, []
        check[pi-1] = True
        while pi != p[curr-1]:
            check[curr-1] = True
            cycle.append(c[curr-1])
            curr = p[curr-1]
        check[curr-1] = True
        cycles.append(cycle + [c[curr-1]])

scores = []
for cycle in (np.array(cycle) for cycle in cycles):
    for i in range(cycle.size):
        cum = np.roll(cycle, i).cumsum()
        if cum[-1] > 0 and k > cycle.size:
            scores.append(cum[-1]*(k//cycle.size-1) + np.concatenate([cum, cum[:k % cycle.size]+cum[-1]]).max())
        else:
            scores.append(cum[:min(k, cum.size)].max())

print(max(scores))

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
v = []
for n in range(N):
    loop, score = 0, 0
    t = n
    for i in range(min(N,K)):
        n = P[n] - 1
        score += C[n]
        ans = max(ans,score)
        if n == t:
            loop = i + 1
            break
    v.append((loop,score))
    
    
for n in range(N):
    loop,score = v[n]
    if loop > 0 and score > 0:
        r = (K-1)//loop
        nscore = r*score
        for i in range(K - r*loop):
            n = P[n] - 1
            nscore += C[n]
            ans = max(nscore, ans)
            
print(ans)

Solution (Python):
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))

    ans=-10**18
    for i in range(n):
        start,count=i,1
        val=c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]
        start = i
        if val > 0:
            a = (k//count-1)*val
            ans=max(a,ans)
            num=count+k%count
        else:
            a=0
            num=min(k,count)
        for _ in range(num):
            a += c[start]
            start=p[start]-1
            ans=max(a,ans)
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from numba import jit
@jit
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))

    ans=-10**18
    for i in range(n):
        start,count=i,1
        val=c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]
        start = i
        if val > 0:
            a = (k//count-1)*val
            ans=max(a,ans)
            num=count+k%count
        else:
            a=0
            num=min(k,count)
        for _ in range(num):
            a += c[start]
            start=p[start]-1
            ans=max(a,ans)
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from numba import jit
@jit
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))

    ans=-10**18
    for i in range(n):
        start,count=i,1
        val=c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]
        start = i
        if val > 0:
            a = (k//count-1)*val
            ans=max(a,ans)
            num=count+k%count
        else:
            a=0
            num=min(k,count)
        for _ in range(num):
            a += c[start]
            start=p[start]-1
            ans=max(a,ans)
    print(ans)
main()

Solution (Python):
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))

ans=-10**18
for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]
    start = i
    if val > 0:
        a = (k//count-1)*val
        ans=max(a,ans)
        num=count+k%count
    else:
        a=0
        num=min(k,count)
    for _ in range(num):
        a += c[start]
        start=p[start]-1
        ans=max(a,ans)
print(ans)

Solution (Python):
from typing import List

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve(N: int, K: int, P: List[int], C: List[int]):
    ans = max(C)
    visited = [False] * N
    for i in range(N):
        if visited[i]:
            continue

        cycle = []
        to = i
        while not visited[to]:
            visited[to] = True
            cycle.append(C[to])
            to = P[to] - 1

        ans = max(ans, partial_solve(len(cycle), K, cycle))

    return ans


def partial_solve(N: int, K: int, A: List[int]):
    ret = max(A)
    B = [0] * (3 * N + 1)
    for i in range(1, 3 * N + 1):
        B[i] = B[i - 1] + A[(i - 1) % N]

    if N > K:
        for l in range(1, N + 1):
            for r in range(l, l + K):
                ret = max(ret, B[r] - B[l - 1])

    else:
        if B[N] < 0:
            K = N
            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])
        else:
            cnt = K // N - 1

            K = K % N + N

            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])

            ret += cnt * B[N]

    return ret

print(solve(N, K, P, C))

Solution (Python):


from numba import njit,i8
import numpy as np


n,k = map(int,input().split())
p = np.array([int(i)-1 for i in input().split()],np.int64)
c = np.array(list(map(int,input().split())),np.int64)

@njit(i8(i8,i8[:],i8[:]), cache = True)
def calc_score(x,p,c):
    n = p.size
    score = 0
    score_list = np.zeros(n,np.int64)
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_list[cnt-1] = score
        else:
            return score_list[:k].max()
    
    if score>0:
        tmp = np.arange(cnt)
        return (score_list[tmp] + ((k-1-tmp)//cnt) * score).max()
    else:
        return score_list[:cnt].max()

ans = max(calc_score(i,p,c) for i in range(n))
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)

ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

print(ans)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
dic = {}
for i in range(1, n+1):
  dic[i] = [p[i-1], c[i-1]]
INF = 10**20
ans = -INF
for j in range(1, n+1):
  state = [True] * 5001
  max_score = -INF
  max_idx = 0
  score = 0
  now = dic[j][0]
  cnt = 0
  lst = []
  flg = True
  for _ in range(k):
    if not state[now]:
      flg = False
      break
    score += dic[now][1]
    cnt += 1
    if max_score < score:
      max_score = score
      max_idx = cnt
    lst.append(score)
    state[now] = False
    now = dic[now][0]
  if score <= 0 or flg:
    ans = max(max_score, ans)
  else:
    q = k // cnt
    r = k % cnt
    if r >= max_idx:
      x = score * q + max_score
      ans = max(ans, x)
    else:
      if q >= 1:
        if r == 0:
          x = score * (q - 1) + max_score
          ans = max(ans, x)
        else:
          x = score * (q - 1) + max_score
          y = score * q + max(lst[:r])
          ans = max(ans, x, y)
      else:
        ans = max(ans, max_score)
print(ans)

Solution (Python):
n, k = list(map(int, input().split()))

p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -float('inf')

for si in range(1, n+1):

    
    x = si
    s = list()  
    
    tot = 0     
    while 1:
        x = p[x]
        s.append(c[x])
        
        
        tot += c[x]
        if (x == si): break 
    
    
    s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   
        if (i+1 > k): break 
        
        if tot > 0:
            e = (k-(i+1))//s_len 
            now = t + tot*e      
        else:
            now = t
        ans = max(ans, now)

print(ans)

Solution (Python):
from numba import jit
@jit
def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: 
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val 
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()

Solution (Python):
import sys
input = sys.stdin.readline


N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


P.insert(0, 0)
C.insert(0, 0)


groups = []
appeared = set()

for i in range(1, N + 1):
	if not i in appeared:
		group = []
		s = set()
		j = i

		while not j in s:
			group.append(j)
			s.add(j)
			appeared.add(j)
			j = P[j]

		groups.append(group)

minus_max = -sys.maxsize
ans = minus_max


for group in groups:
	n = len(group)

	
	for g in group:
		score = 0
		max_score = minus_max
		scores = []
		scores.append(minus_max)
		Pi = P[g]

		for j in range(n):
			score += C[Pi]
			max_score = max(max_score, score)
			scores.append(max_score)
			Pi = P[Pi]

		if K > n and score > 0:
			s = scores[K % n] + score * (K // n)
			ans = max(ans, s)

			s = scores[n] + score * (K // n - 1)
			ans = max(ans, s)
		elif K > n:
			ans = max(ans, scores[n])
		else:
			ans = max(ans, scores[K])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


P.insert(0, 0)
C.insert(0, 0)


groups = []
appeared = set()

for i in range(1, N + 1):
	if not i in appeared:
		group = []
		s = set()
		j = i

		while not j in s:
			group.append(j)
			s.add(j)
			appeared.add(j)
			j = P[j]

		groups.append(group)

MIN = -sys.maxsize
ans = MIN


for group in groups:
	n = len(group)

	
	for g in group:
		score = 0
		max_score = MIN
		scores = []
		scores.append(MIN)
		Pi = P[g]

		for j in range(n):
			score += C[Pi]
			max_score = max(max_score, score)
			scores.append(max_score)
			Pi = P[Pi]

		if K > n and score > 0:
			s = scores[K % n] + score * (K // n)
			ans = max(ans, s)

			s = max_score + score * (K // n - 1)
			ans = max(ans, s)
		elif K > n:
			ans = max(ans, max_score)
		else:
			ans = max(ans, scores[K])

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)


INF=10**20
def solve(N: int, K: int, P: "List[int]", C: "List[int]"):
    ans = -INF
    for i in range(N):
        start = i + 1 
        stack = [start]
        score_his = [0]
        scores = 0
        depth = 1
        seen = {}
        while stack:
            if depth > K: break
            current = stack.pop()
            
            if current in seen:
                loop_start_depth = seen[current]
                loop_end_depth = depth - 1 
                loop_scores = score_his[-1] - score_his[loop_start_depth-1]
                loop_len = loop_end_depth - loop_start_depth + 1
                if loop_scores < 0: break
 
                
                
                
                rest_count = K - depth + 1
                available_loop_count = rest_count // loop_len
                res1 = (available_loop_count-1) * loop_scores + scores
 
                
                
                res2 = res1
                rest_loop_len = rest_count % loop_len + loop_len
 
                
                ress = [res1,res2]
                for j in range(rest_loop_len):
                    score = C[P[current-1]-1]
                    res2 += score
                    ress.append(res2)
                    current = P[current-1]
 
                
                score_his.append(max(ress))
 
                break
 
            
            score = C[P[current-1]-1]
            scores += score
            score_his.append(scores)
 
            seen[current] = depth
            stack.append(P[current-1])
 
            depth += 1
        
        ans = max(ans,max(score_his[1:]))
    
    print(ans)
 
 
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    P = [int(next(tokens)) for _ in range(N)]  
    C = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, P, C)



if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

g = [v for v in range(n + 1)]
s = [0] * (n + 1)
r = [0] * (n + 1)
seen = set()
for i in range(1, n + 1):
    if i in seen:
        s[i] = s[g[i]]
        r[i] = r[g[i]]
        continue
    ni = i
    sm = 0
    cnt = 0
    while True:
        ni = p[ni]
        sm += c[ni]
        cnt += 1
        g[ni] = i
        seen.add(ni)
        if ni == i:
            break
    s[i] = sm
    r[i] = cnt

ans = -(10 ** 9 + 1)
for i in range(1, n + 1):
    ni = i
    sm = 0
    cnt = 0
    while True:
        ni = p[ni]
        sm += c[ni]
        cnt += 1
        ans = max(ans, sm, sm + (k - cnt) // r[i] * s[i])
        if ni == i or cnt == k:
            break
print(ans)

Solution (Python):

import sys
from collections import defaultdict

sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, PS, CS):
    PS = [x - 1 for x in PS]
    CS = [CS[PS[i]] for i in range(N)]
    visited = {}
    loops = []
    loopScore = []
    for i in range(N):
        loop = []
        c = 0
        while i not in visited:
            visited[i] = True
            c += CS[i]
            i = PS[i]
            loop.append(i)
        if loop:
            loops.append(loop)
            loopScore.append(c)

    pos = list(range(N))
    ret = -INF
    for i, loop in enumerate(loops):
        if loopScore[i] > 0:
            baseScore = loopScore[i] * (K // len(loop))
            r = K % len(loop)
            if r == 0:
                r = len(loop)
                baseScore -= loopScore[i]
            maxscore = 0
            scores = defaultdict(int)
            for i in range(r):
                for x in loop:
                    scores[x] += CS[pos[x]]
                    pos[x] = PS[pos[x]]
                maxscore = max(maxscore, max(scores.values()))
            ret = max(maxscore + baseScore, ret)
        else:
            r = len(loop)
            maxscore = -INF
            scores = defaultdict(int)
            for i in range(r):
                for x in loop:
                    scores[x] += CS[pos[x]]
                    pos[x] = PS[pos[x]]
                maxscore = max(maxscore, max(scores.values()))
            ret = max(maxscore, ret)

    return ret


def main():
    
    N, K = map(int, input().split())
    PS = list(map(int, input().split()))
    CS = list(map(int, input().split()))
    print(solve(N, K, PS, CS))



T1 = """
5 2
2 4 5 1 3
3 4 -10 -8 8
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
8
"""

T2 = """
2 3
2 1
10 -7
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13
"""

T3 = """
3 3
3 1 2
-1000 -2000 -3000
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
-1000
"""

T4 = """
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
29507023469
"""

T5 = """
3 1000
2 3 1
1 0 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
1001
"""

T6 = """
3 1000
2 3 1
1 1 -3
"""
TEST_T6 = """
>>> as_input(T6)
>>> main()
2
"""

T7 = """
4 1000
2 1 4 3
1 1 -10000 10000
"""
TEST_T7 = """
>>> as_input(T7)
>>> main()
10000
"""

T8 = """
4 1000
2 1 4 3
1 1 -10000 10001
"""
TEST_T8 = """
>>> as_input(T8)
>>> main()
10500
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve0(N, K, PS, CS):
    PS = [x - 1 for x in PS]
    debug(": PS", PS)
    CS = [CS[PS[i]] for i in range(N)]
    PSS = [PS]
    CSS = [CS]
    prevPS = PS
    prevCS = CS
    for i in range(30):
        PS2 = [prevPS[prevPS[i]] for i in range(N)]
        CS2 = [prevCS[i] + prevCS[prevPS[i]] for i in range(N)]
        PSS.append(PS2)
        CSS.append(CS2)
        prevPS = PS2
        prevCS = CS2

    score = [0] * N
    pos = list(range(N))
    length = [0] * N
    maxbit = K.bit_length() - 1
    for i in range(maxbit, -1, -1):
        
        
        
        
        
        
        for j in range(N):
            
            
            if length[j] + 2 ** i <= K and CSS[i][pos[j]] > 0:
                
                score[j] += CSS[i][pos[j]]
                pos[j] = PSS[i][pos[j]]
                length[j] += 2 ** i
            
            
            
            
            
            

    
    ret = max(score)
    if ret == 0:
        ret = max(CS)
    return ret


def solve(N, K, PS, CS):
    PS = [x - 1 for x in PS]
    CS = [CS[PS[i]] for i in range(N)]
    visited = {}
    loops = []
    loopScore = []
    for i in range(N):
        loop = []
        c = 0
        while i not in visited:
            visited[i] = True
            c += CS[i]
            i = PS[i]
            loop.append(i)
        if loop:
            loops.append(loop)
            loopScore.append(c)
    
    
    scores = [0] * N
    pos = list(range(N))
    from collections import defaultdict

    ret = 0
    for i, loop in enumerate(loops):
        if loopScore[i] > 0:
            baseScore = loopScore[i] * (K // len(loop))
            r = K % len(loop)
            if r == 0:
                r = len(loop)
                baseScore -= loopScore[i]
                
            maxscore = 0
            scores = defaultdict(int)
            for i in range(r):
                for x in loop:
                    scores[x] += CS[pos[x]]
                    pos[x] = PS[pos[x]]
                maxscore = max(maxscore, max(scores.values()))
                
            ret = max(maxscore + baseScore, ret)
        else:
            r = len(loop)
            maxscore = -INF
            scores = defaultdict(int)
            for i in range(r):
                for x in loop:
                    scores[x] += CS[pos[x]]
                    pos[x] = PS[pos[x]]
                
                maxscore = max(maxscore, max(scores.values()))
            ret = max(maxscore, ret)

    if ret == 0:
        ret = max(CS)
    return ret


def main():
    
    N, K = map(int, input().split())
    PS = list(map(int, input().split()))
    CS = list(map(int, input().split()))
    print(solve(N, K, PS, CS))



T1 = """
5 2
2 4 5 1 3
3 4 -10 -8 8
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
8
"""

T2 = """
2 3
2 1
10 -7
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13
"""

T3 = """
3 3
3 1 2
-1000 -2000 -3000
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
-1000
"""

T4 = """
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
29507023469
"""

T5 = """
3 1000
2 3 1
1 0 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
1001
"""

T6 = """
3 1000
2 3 1
1 1 -3
"""
TEST_T6 = """
>>> as_input(T6)
>>> main()
2
"""

T7 = """
4 1000
2 1 4 3
1 1 -10000 10000
"""
TEST_T7 = """
>>> as_input(T7)
>>> main()
10000
"""

T8 = """
4 1000
2 1 4 3
1 1 -10000 10001
"""
TEST_T8 = """
>>> as_input(T8)
>>> main()
10001
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    loop = accum[l-1]
    accum=[0]+accum
    for x in range(1,l+1):
        if loop<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

def solve():
    N, K = map(int, readline().split())
    P = [v - 1 for v in map(int, readline().split())]
    C = list(map(int, readline().split()))


    ans = -10**10

    for i in range(N):
        moves = 1
        cur = P[i]
        score = C[cur]
        ans = max(score, ans)
        visited = {cur: (moves, score)}

        while P[cur] not in visited and moves < K:
            cur = P[cur]
            moves += 1
            score += C[cur]
            visited[cur] = (moves, score)

            ans = max(ans, score)
        
        if moves == K:
            continue
        
        cur = P[cur]
        moves += 1
        score += C[cur]

        T = moves - visited[cur][0]
        D = score - visited[cur][1]

        if D < 0:
            continue
        
        nloops = K - moves
        moves += T * (nloops // T)
        score += D * (nloops // T)

        ans = max(ans, score)

        while moves < K:
            cur = P[cur]
            moves += 1
            score += C[cur]
            ans = max(ans, score)
    
    print(ans)

solve()

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -10**18

for i in range(N):
    now = i
    visit = [False]*N
    visit[now] = True
    l = []
    
    while True:
        nex = P[now]-1
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    s = sum(l)
    acc = 0
    
    for j in range(min(K, len(l))):
        acc += l[j]
        ans = max(ans, acc+max(0, (K-j-1)//len(l)*s))

print(ans)

Solution (Python):
def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    for i in range(N):
        P[i] -= 1

    ans = -1e18
    for i in range(N):
        n = P[i]
        score = C[n]
        t = [score]
        while n != i:
            n = P[n]
            score += C[n]
            t.append(score)

        total = t[-1]
        l = len(t)
        for i in range(min(K, l)):
            temp_score = t[i]
            if total > 0 and K > l:
                e = int((K-(i+1))/l)
                temp_score += total*e
            ans = max(ans, temp_score)

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n,k = rm()
p = rl()
p = [0]+p
c = rl()
c = [0]+c
b = [-1]*(n+1)
give=0
ans=-math.inf

for i in range(1,n+1):
    a=i
    lenn=1
    add=c[i]
    while p[a]!=i:
        add+=c[p[a]]
        lenn+=1
        a=p[a]
    if add<0:
        add=0
    addAgain=0
    a=i
    for j in range(lenn):
        if j>k:
            break
        addAgain+=c[a]
        ans = max(ans, addAgain+add*((k-j-1)//lenn))
        a = p[a]

print(ans)