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
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
def main():
    n, k = map(int, input().split())
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    if k == 1:
        print(max(c))
        sys.exit()
    seen = [0] * n
    cycles = []
    for i1 in range(n):
        if not seen[i1]:
            cycle_t = []
            koko = i1
            while True:
                if seen[koko]:
                    cycles.append(cycle_t)
                    break
                cycle_t.append(c[koko])
                seen[koko] = 1
                koko = p[koko] - 1

    score = max(c)
    for cycle in cycles:
        score_t = max(cycle)
        cycle_len = len(cycle)
        cycle_sum = sum(cycle)
        kaisu, rem = divmod(k, cycle_len)
        if rem == 0:
            kaisu -= 1
            rem = cycle_len
        if kaisu > 0:
            kaisu -= 1
            rem += cycle_len
        cycle = tuple(accumulate(cycle + cycle + cycle))
        for i1 in range(2, rem + 1):
            for i2 in range(cycle_len):
                score_t = max(score_t, cycle[i1+i2] - cycle[i2])
        if cycle_sum > 0:
            score_t += (kaisu * cycle_sum)
        score = max(score, score_t)
    print(score)

if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
p=[x-1 for x in p]
mi=set(range(n))
g={}

while mi:
  x0=mi.pop()
  ary=[c[x0]]
  x=x0
  while p[x]!=x0:
    x=p[x]
    mi.discard(x)
    ary.append(c[x])
  cnt=len(ary)
  tmp=0
  ary*=2
  cary=[tmp]
  for x in ary:
    tmp+=x
    cary.append(tmp)
  g[x0]=[cnt,cary]
ans=-float('inf')
for cnt,cary in g.values():
  x,y=divmod(k,cnt)
  tmp1=max(0,cary[cnt]*x)
  tmp2=-float('inf')
  for i in range(cnt):
    for j in range(y):
      tmp2=max(tmp2,cary[i+j+1]-cary[i])
  ans=max(ans,tmp1+tmp2)
  if x:
    tmp1=max(0,cary[cnt]*(x-1))
    tmp2=-float('inf')
    for i in range(cnt):
      for j in range(cnt):
        tmp2=max(tmp2,cary[i+j+1]-cary[i])
    ans=max(ans,tmp1+tmp2)
  

print(ans)

Solution (Python):
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    P = [p]
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
        P.append(p)
    front = P[:L]
    if L != N:
        cycle, end = P[L:R], P[L:L+(N-L)%period]
        cnt = (N-L)//period
    return front, cycle, end, cnt




import sys
input = sys.stdin.readline
from itertools import accumulate

def lift(x): return P[x-1]

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
res = -float("inf")
for i in range(1,N+1):
    front, cycle, end, cnt = cycle_getter(K,i)
    S = sum(C[j-1] for j in front)
    T = sum(C[j-1] for j in cycle)
    if cycle+end:
        U = max(0, max(accumulate(C[j-1] for j in cycle+end)))
    else: U=0
    if front:
        R = max(accumulate(C[j-1] for j in front))
    else: R=0
    res = max(res, S+T*(cnt-1)+U, S+U, R)
print(res)

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

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

print(ans)

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



for s in range(0,N):
    k=K-1
    score=0
    s=P[s]
    score+=C[s]
    count=1
    idle_max=max(idle_max,score)
    visited={s:[count,score]}
    while k and not P[s] in visited:

        k-=1
        count+=1
        s=P[s]
        score+=C[s]
        visited[s]=[count,score]

        idle_max=max(idle_max,score)
    
    if k:
        c1,score1=visited[s]
        c2,score2=visited[P[s]]
        c1+=1
        s=P[s]
        score1+=C[s]
        score+=C[s]
        k-=1


        n=c1-c2
        score+=(score1-score2)*(k//n)
        k%=n
        idle_max=max(idle_max,score)
    while k:
        k-=1
        s=P[s]
        score+=C[s]
        idle_max=max(idle_max,score)


print(idle_max)

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 = [int(p) for p in input().split()]
C = [int(c) for c in input().split()]

ans = max(C)
for i in range(N):
    used = [0]*N
    used[i] = 1
    loop = [C[i]]
    j = P[i]-1
    while used[j] == 0:
        used[j] = 1
        loop.append(loop[-1]+C[j])
        j = P[j]-1
    M = len(loop)
    if K >= M:
        if K%M == 0:
            t = 0
        else:
            t = max(loop[:K%M])
            t = max(t, 0)
        num = max(loop[-1]*(K//M)+t, max(loop), loop[-1]*(K//M-1)+max(loop))
    else:
        num = max(loop[:K])
    ans = max(ans, num)
if max(C) <= 0:
    ans = max(C)
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(lambda x : int(x) - 1, input().split()))
c=list(map(int,input().split()))
s=[0]*(n+1)
ans=-float("inf")
for i in range(n):
    x = i
    tmp = [-10 ** 9] * (n + 1)
    for j in range(1, n + 1):
        s[j] = s[j - 1] + c[p[x]]
        tmp[j] = max(tmp[j-1], s[j])
        x = p[x]
        if x == i:
            break
    if j >= k:
        ans = max(ans, tmp[k])
    elif s[j] < 0:
        ans = max(ans, tmp[j])
    else:
        m = k // j
        a = s[j] * (m - 1) + tmp[j]
        b = s[j] * m + tmp[k % j]
        ans = max(ans, a, b)
print(ans)

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

point_loop_list = [0 for _ in range(N)]
point_set = set()
loop_list = []
for i in range(N):
    if i in point_set:
        continue
    loop = [i]
    j = P[i] - 1
    while j != i:
        loop.append(j)
        point_set.add(j)
        j = P[j] - 1
    loop += loop
    loop_list.append(loop)



loop_sum_list = [0 for _ in range(N)]

for loop in loop_list:
    loop_len = len(loop) // 2
    s = sum([C[j] for j in loop[:loop_len]])

    for i, p in enumerate(loop[:loop_len]):
        point_loop_list[p] = loop[i:i+loop_len]
        loop_sum_list[p] = s


ans = min(C)

for l, s in zip(point_loop_list, loop_sum_list):
    p = 0
    loop_len = len(l)
    if s > 0:
        num_loop = K // loop_len if K % loop_len != 0 else K // loop_len - 1
        p += s * num_loop
        m = 0
        cs = 0
        for i in range(K - loop_len * num_loop):
            cs += C[l[i]]
            m = max(m, cs)
        p += m
    else:
        m = C[l[0]]
        cs = m
        for i in range(1, loop_len):
            cs += C[l[i]]
            m = max(m, cs)
        p += m
    ans = max(p, ans)

print(ans)

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

P = [p - 1 for p in P]

def max_point(p, k):
    point = p
    visited = set()
    visited_record = []
    score = 0
    scores = []
    while point not in visited:
        visited.add(point)
        visited_record.append(point)
        score += C[point]
        scores.append(score)
        
        point = P[point]
    else:
        loop_entry_index = visited_record.index(point)
        loop_len = len(visited_record) - loop_entry_index
        if loop_entry_index > 0:
            loop_score = scores[-1] - scores[loop_entry_index-1]
        else:
            loop_score = scores[-1]
        head_len = loop_entry_index
    

    if k <= len(scores):
        return max(scores[:k])
    else:
        if loop_score > 0:
            k -= head_len
            scores = scores[:head_len]
            quotient = k // loop_len
            reminder = k % loop_len
            
            if scores == []:
                score = 0
            else:
                score = scores[head_len-1]
            score += (quotient - 1) * loop_score
            point = visited_record[loop_entry_index]
            for i in range(loop_len + reminder):
                score += C[point]
                scores.append(score)
                
                point = P[point]
            return max(scores)
        else:
            
            return max(scores)



point = -float("inf")
for p in P:
    point = max(max_point(p, k), point)
print(point)

Solution (Python):
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N+1):
    v = i
    score = 0
    size = 0
    while True:
        size += 1
        score += C[v]
        if i == P[v]:
            break
        v = P[v]

    if score > 0:
        tmp = score*(K//size-1)
        num = K%size+size
    else:
        tmp = 0
        num = min(K, size)
    
    v = i
    for _ in range(num):
        tmp += C[v]
        v = P[v]
        ans = max(tmp, ans)

print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(n):
  ct=0
  score=0
  s=[]
  pos=i
  while ct<k:
    ct+=1
    pos=p[pos]-1
    score+=c[pos]
    s.append(score)
    if pos==i:
      break
  if s[-1]<0:
    ans.append(max(s))
  elif pos!=i:
    ans.append(max(s))
  elif k%len(s)==0:
    ans.append(s[-1]*(k//len(s)-1)+max(s))
  else:
    ans.append(max(s[-1]*(k//len(s)-1)+max(s),s[-1]*(k//len(s))+max(s[0:k%len(s)])))
print(max(ans))

Solution (Python):
N, K = map(int, input().split())
P = list(map(lambda x:int(x) - 1,input().split()))
C = list(map(int, input().split()))
ans = -10**9

for i in range(N):
    tmp_max = [-10**9]*(N+1)
    total = 0
    current_block = P[i]
    for j in range(1, N + 1):
        total += C[current_block]
        tmp_max[j] = max(tmp_max[j-1], total)
        if current_block == i:
            break
        current_block = P[current_block]
    if total <= 0:
        ans = max(ans, tmp_max[j])
    else:
        n = K // j
        r = K % j
        if r == 0:
            ans = max(ans, total*(n-1) + tmp_max[j])
        else:
            ans = max(ans, total*n + tmp_max[r])

print(ans)

Solution (Python):
N, K = map(int, input().split())
moves = [0] + list(map(int, input().split()))
points = [0] + list(map(int, input().split()))
INF = 10**10
 
answer = -INF
for start in range(1, N+1):
  circle = [start]
  next = moves[start]
  c_score = points[start]
  while(next != start):
    circle.append(next)
    c_score += points[next]
    next = moves[next]
  m_score = 0
  for i in range(min(len(circle), K)):
    m_score += points[circle[i]]
    loop_cnt = (K-i-1)//len(circle)
    answer = max(answer, m_score + max(0, loop_cnt * c_score))
print(answer)

Solution (Python):
from numba import jit

@jit
def solve():
    n, k = map(int,input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    max_score = -10**10

    for i in range(n):
        count = 1
        val = c[i]

        next_i = p[i] -1
        while next_i != i:
            count += 1
            val += c[next_i]
            next_i = p[next_i] - 1
        
        if val > 0:
            loop_num = (k//count -1)
            tmp_score = loop_num * val
            max_score = max(tmp_score, max_score)
            num = k%count+count

        else:
            tmp_score = 0
            num = min(k, count)

        next_i = i
        for _ in range(num):
            next_i = p[next_i] - 1
            tmp_score += c[next_i]
            max_score = max(tmp_score, max_score)
    
    print(max_score)

solve()

Solution (Python):

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
k_max = 10100
score = [-10**18-1] * N

for i in range(N):
  score_i = [-10**18-1] * k_max 
  score_i[0] = C[P[i]-1]
  index = P[i]-1
  for k in range(1, K):
    if index == i:
      
      
      loop_score = score_i[k-1] 
      if loop_score > 0:
        loop_num = k 
        
        tmp_score = [-10**18-1] * k_max
        tmp_score[0] = (K//k -1) * loop_score


        tmp_index = index

        for j in range (1, loop_num + K%k + 1):
          tmp_score[j] = tmp_score[j-1] + C[P[tmp_index]-1]
          tmp_index = P[tmp_index]-1

        score_i[k] = max(tmp_score)
      break
    score_i[k] = score_i[k-1] + C[P[index]-1]
    index = P[index]-1
  score[i] = max(score_i)
print(max(score))

Solution (Python):
INF = float("inf")

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

ans = -INF
for s in range(N):
    
    cum = []
    i = P[s] - 1 
    cum.append(C[i])
    while i != s:
        i = P[i] - 1
        cum.append(cum[-1] + C[i])
    

    
    if K <= len(cum):
        
        score = max(cum[:K])
    
    elif cum[-1] <= 0:
        
        score = max(cum)
    else:
        
        score1 = cum[-1] * (K//len(cum) - 1)
        score1 += max(cum)

        
        score2 = cum[-1]*(K//len(cum))
        resi = K % len(cum) 
        if resi != 0:
            
            score2 += max(0, max(cum[:resi]))
        score = max(score1, score2)
    
    ans = max(ans, score)

print(ans)

Solution (Python):
N,K = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -1* 10**9

for si in range(N):
  s = list()
  total = 0
  l = 0
  x = si
  while(1):
    x = p[x] - 1
    s.append(c[x])
    total += c[x]
    l += 1
    if x == si:
      break
  t = 0
  for j in range(l):
    t += s[j]
    now = t
    if j >= K:
      break
    if total > 0:
      e = (K-j-1)//l
      now += total * e
    ans = max(ans, now)

print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=list(map(lambda x:x-1,P)) 
C=list(map(int,input().split()))
ans=-float("inf")
for i in range(N):
   st=i
   tmp=0
   for j in range(K):
      st=P[st]
      tmp+=C[st]
      ans=max(ans,tmp)
      if i==st:
         break
   s,v=divmod(K,j+1)
   if s>1 and v==0:
      s-=1
      v=j+1
   tmp*=s
   ans=max(ans,tmp)
   for j in range(v):
      st=P[st]
      tmp+=C[st]
      ans=max(ans,tmp)
print(ans)

Solution (Python):
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
ps = [p-1 for p in ps]

vers = []   
score = []  
vers.append(ps)
score.append(cs)

m = 31

for b in range(1, m+1):
    p_bth = [0] * n
    c_bth = [0] * n
    for i in range(n):
        p_bth[i] = vers[b-1][vers[b-1][i]]
        c_bth[i] = score[b-1][i] + score[b-1][vers[b-1][i]]
    vers.append(p_bth)
    score.append(c_bth)


MIN = -(1 << 63) 
prv = [[MIN, 0] for _ in range(n)]
nxt = [[MIN, MIN] for _ in range(n)] 
for b in range(m, -1, -1):
    for i in range(n):
        if (k >> b) & 1:
            nxt[vers[b][i]][0] = max(nxt[vers[b][i]][0], prv[i][0] + score[b][i])
            nxt[vers[b][i]][1] = max(nxt[vers[b][i]][1], prv[i][1] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
        else:
            nxt[vers[b][i]][0] = max(nxt[vers[b][i]][0], prv[i][0] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0])
            nxt[i][1] = max(nxt[i][1], prv[i][1])
    prv, nxt = nxt, prv

ans = max(max(x) for x in prv)
if ans == 0:
    ans = max(cs)
print(ans)

Solution (Python):
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 21
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve(n=None, s1=None, s2=None):
    n, k = getList()
    pli = getList()
    cli = getList()

    ans = max(cli)
    for i in range(n):
        cycle = [i]
        pts = [cli[i]]
        pos = i
        while True:
            pos = pli[pos] - 1
            if pos != i:
                cycle.append(pos)
                pts.append(cli[pos])
            else:
                break
        lc = len(cycle)
        acc = 0
        sumpts = sum(pts)
        for j in range(lc):
            acc += pts[j]

            if sumpts > 0:
                around = (k - j - 1) // lc
                tmp = acc + sumpts * around
            else:
                tmp = acc
            ans = max(ans, tmp)

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    
    solve()

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))

INF = 1001001001





n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

print(ans)

Solution (Python):
N, K = map(int, input().split())
moves = [0] + list(map(int, input().split()))
points = [0] + list(map(int, input().split()))
INF = 10**10

answer = -INF
for start in range(1, N+1):
  circle = [start]
  next = moves[start]
  c_score = points[start]
  while(next != start):
    circle.append(next)
    c_score += points[next]
    next = moves[next]
  m_score = 0
  for i in range(min(len(circle), K)):
    m_score += points[circle[i]]
    loop_cnt = (K-i-1)//len(circle)
    answer = max(answer, m_score + max(0, loop_cnt * c_score))
print(answer)

Solution (Python):

import bisect

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

F=[0]*N

def search(n):
    res=[]
    l=0
    m=n
    tmp_res=0
    isloop=0
    if F[n-1]:
        s,L=F[n-1]
    while 1:
        m=P[m-1]
        tmp_res+=C[m-1]
        l+=1
        if F[n-1]==0:
            res.append((tmp_res,l))
        else:
            res.append(tmp_res+s*((K-l)//L) if s>0 and K>=l else tmp_res)
        if m==n:
            isloop=1
            break
        if l==K:
            break
    if F[n-1]==0:
        if isloop:
            s,L=res[-1]
            if not F[n-1]:
                m=n
                while 1:
                    F[m-1]=(s,L)
                    m=P[m-1]
                    if m==n:
                        break
        else:
            s=-1
        p=max([p+s*((K-k)//len(res)) if s>0 and K>=k else p for p,k in res])
    else:
        p=max(res)
    return p

res=-float('inf')
for i in range(N):
    res=max(res,search(i+1))
print(res)

Solution (Python):
def solve():
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    *C, = map(int, input().split())
    ans = -float("inf")

    for pos in range(N):
        used = [-1] * N
        cost = [0] * (N+1)

        for k in range(N+1):
            if k:
                cost[k] = cost[k-1] + C[pos]
            if used[pos] >= 0:
                loop_size = k-used[pos]
                break
            used[pos] = k
            pos = P[pos] - 1
        if cost[loop_size] <= 0:
            ans = max(ans, max(cost[1:K+1]))
        else:
            a, b = divmod(K, loop_size)
            v1 = cost[loop_size] * (a-1) + max(cost[:K+1])
            v2 = cost[loop_size] * a + max(cost[:b+1])
            ans = max(ans, max(v1, v2) if a else v2)

    print(ans)

solve()

Solution (Python):
N, K = map(int, input().split())
*P, = map(int, input().split())
*C, = map(int, input().split())
ans = -float("inf")

for pos in range(N):
    used = [-1] * N
    cost = [0] * (N+1)

    for k in range(N+1):
        if k:
            cost[k] = cost[k-1] + C[pos]
        if used[pos] >= 0:
            loop_size = k-used[pos]
            break
        used[pos] = k
        pos = P[pos] - 1
    if cost[loop_size] <= 0:
        ans = max(ans, max(cost[1:K+1]))
    else:
        a, b = divmod(K, loop_size)
        v1 = cost[loop_size] * (a-1) + max(cost[:K+1])
        v2 = cost[loop_size] * a + max(cost[:b+1])
        ans = max(ans, max(v1, v2) if a else v2)

print(ans)

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

def get(pos):
    used = [-1] * N
    cost = [0] * (N+1)

    for k in range(N+1):
        if k:
            cost[k] = cost[k-1] + C[pos]
        if used[pos] >= 0:
            loop_size = k-used[pos]
            break
        used[pos] = k
        pos = P[pos] - 1
    if cost[loop_size] <= 0:
        return max(cost[1:K+1])
    else:
        a, b = divmod(K, loop_size)
        v1 = cost[loop_size] * (a-1) + max(cost[:K+1])
        v2 = cost[loop_size] * a + max(cost[:b+1])
        return max(v1, v2) if a else v2

ans = max([get(i) for i in range(N)])
print(ans)

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

def get(pos):
    used = [-1] * N
    cost = [0] * (N+1)

    for k in range(N+1):
        if k:
            cost[k] = cost[k-1] + C[pos]
        if used[pos] >= 0:
            loop_size = k-used[pos]
            break
        used[pos] = k
        pos = P[pos] - 1
    if cost[loop_size] <= 0:
        return max(cost[1:K+1])
    else:
        v2 = cost[loop_size] * (K//loop_size) + max(cost[:(K%loop_size)+1])
        if K//loop_size:
            v1 = cost[loop_size] * ((K//loop_size)-1) + max(cost[:K+1])
            return max(v1, v2)
        else:
            return v2

ans = max([get(i) for i in range(N)])
print(ans)

Solution (Python):
from sys import stdin
n,k = map(int,stdin.readline().split())
p = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))

ans = -float("inf")
def helper(index):
    visited  = {index}
    looplen = 1
    looptotal = c[index]
    while p[index]-1 not in visited:
        nextindex = p[index] - 1
        looplen += 1
        looptotal += c[nextindex]
        visited.add(nextindex)
        index = nextindex
    return (looplen,looptotal)

for i in range(n):
    looplen,looptotal = helper(i)
    if looptotal >= 0:
        cur = looptotal*((k//looplen)-1) if k >= looplen else 0
        remain = looplen + (k%looplen) if k >= looplen else k
    else:
        cur = 0
        remain = looplen
    curmax = -float("inf")
    curindex = i
    for _ in range(remain):
        nextindex = p[curindex]-1
        cur += c[nextindex]
        curmax = max(curmax,cur)
        curindex = nextindex
    ans = max(ans,curmax)
print(ans)

Solution (Python):
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
p = [i-1 for i in p]


groups = []
is_appear = [False]*n
group_size = [0]*n
for i in range(n):
    if is_appear[i]:
        continue
    group = []
    group.append(i)
    is_appear[i] = True
    j = p[i]
    while j != i:
        group.append(j)
        is_appear[j] = True
        j = p[j]
        
    groups.append(group)
    
    for i in group:
        group_size[i] = len(group)


cycle_score = [0]*n
for g in groups:
    score = 0
    for i in range(len(g)):
        score += c[g[i]]
    
    for i in g:
        cycle_score[i] = score

best = -float('inf')        
for i in range(n):
    score = 0
    best_i = -float('inf')
    cyc_num = k//group_size[i]
    if cycle_score[i]>0 and cyc_num>=1:
        remain = k-group_size[i]*(cyc_num-1)
        score += cycle_score[i]*(cyc_num-1)
        
    elif cycle_score[i]<=0:
        remain = group_size[i]
    elif cyc_num<1:
        remain = k
    
    j = i
    for _ in range(remain):
        j = p[j]
        score += c[j]
        best_i = max(best_i,score)
    best = max(best,best_i)
    
print(best)

Solution (Python):



import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


def lcm(a, b):
    
    g = gcd(a, b)
    return a // g * b


N, K = ints()
P = mina(*ints())
C = ints()

next = [[-1] * N for _ in range(32)]  
score = [[0] * N for _ in range(32)]  

next[0] = P
for k in range(31):
    for i in range(N):
        next[k + 1][i] = next[k][next[k][i]]

for i in range(N):
    score[0][i] = C[P[i]]
for k in range(31):
    for i in range(N):
        score[k + 1][i] = score[k][i] + score[k][next[k][i]]




def get_score(i, k):  
    now = i
    ret = 0
    for j in range(k.bit_length()):
        if (k >> j) & 1:
            ret += score[j][now]
            now = next[j][now]
    return ret, now



ans = -10**10
for i in range(N):
    
    if K <= N:
        
        tmp = 0
        now = i
        for _ in range(K):
            tmp += score[0][now]
            now = next[0][now]
            ans = max(tmp, ans)
            
    else:
        
        tmp = 0
        now = i
        for j in range(N):
            tmp += score[0][now]
            now = next[0][now]
            ans = max(tmp, ans)
            

        tmp, now = get_score(i, K - N)
        for j in range(N):
            tmp += score[0][now]
            now = next[0][now]
            ans = max(tmp, ans)
            


print(ans)

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

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)