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):
n,k= map(int, input().split())
p= list(map(int, input().split()))
c= list(map(int, input().split()))


ans=-float('inf')


x=[0]*n
for i in range(n):
    if x[i]==0:
        x[i]=1
        y=p[i]-1
        
        aa=[0,c[i]]
        
        life=2
        for j in range(2*n+2):
            x[y]=1
            if life>0:
                aa.append(aa[-1]+c[y])
                y=p[y]-1
                if y==i:
                    life-=1
            else:
                break
        
        x1=(len(aa)-1)//2

        a=[-float('inf')]*(x1+1)

        for ii in range(len(aa)-1):
            for j in range(ii+1,len(aa)):
                if j-ii<=x1:
                    a[j - ii] = max(a[j - ii], aa[j] - aa[ii])

        v=k//x1
        w=k%x1

        if v==0:
            ans=max(ans,max(a[:k+1]))

        elif v==1:

            ans = max(ans, max(a), v * aa[x1] + max(a[:w + 1]))
        else:
            ans=max(ans,max(a),v * aa[x1] + max(a[:w + 1]),(v-1)*aa[x1]+max(a))





print(ans)

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)

for i in range(n):
    uf.union(i,p[i]-1)

ma = float('INF')*(-1)
listcase = []
cc=0
for i in uf.roots():
    st = uf.members(i)[0]
    listcase.append([])
    while True:
        listcase[cc].append(c[st])
        st=p[st]-1
        if st == uf.members(i)[0]:
            break
    cc+=1

for i in listcase:
    m = len(i)
    i2=i*2
    su = 0
    if sum(i)>0:
        su = sum(i)*(k//m)
    m2 = k%m
    if m2==0 and su>0:
        m2=m
        su-=sum(i)
    elif m2==0:
        m2=m
    if sum(i)<=0:
        m2=m
    for l in range(m):
        dp=[float('INF')*(-1)]*(m*2)
        dp[l]=i2[l]
        for j in range(l+1,l+m2):
            dp[j]=max(dp[j-1]+i2[j],i2[j])
        ma = max(ma,su+max(dp))
print(ma)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**10
for i in range(n):
	loop=[0]
	now=i
	while True:
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if now==i:
			break
	L=len(loop)-1
	if k<=L:
		score=max(loop[1:k+1])
		ans=max(score,ans)
	else:
		score=max(loop[-1],0)*(k//L-1)
		ans=max(ans,score)
		for j in range(k%L+L):
			score+=loop[j%L+1]-loop[j%L]
			ans=max(score,ans)
print(ans)

Solution (Python):
from collections import Counter
from heapq import heapify, heappop, heappush
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        scores += scores * 2
        scores.insert(0, 0)
        acc = list(accumulate(scores))

        base = max(0, loop * d)

        range_max = [-a for a in acc[1:m + 1]]
        available_max = Counter(range_max)
        heapify(range_max)
        for i in range(l):
            while available_max[range_max[0]] == 0:
                heappop(range_max)
            ans = max(ans, base - range_max[0] - acc[i])
            old = -acc[i + 1]
            new = -acc[i + m + 1]
            available_max[old] -= 1
            available_max[new] += 1
            heappush(range_max, new)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))

Solution (Python):
from collections import deque
import sys, copy,itertools
input = sys.stdin.readline

n, k = map(int,input().split())

P = list(map(lambda x : int(x) - 1, input().split())) 
C = list(map(int,input().split()))
SCORE = [0]*(n+1)

max_score = -10**12
for i in range(n):
  x = i
  TEMPMAX = [-10**9] * (n+1)
  for j in range(1, n+1):
    SCORE[j] = SCORE[j-1] + C[P[x]]
    TEMPMAX[j]= max(TEMPMAX[j-1], SCORE[j])
    x = P[x]
    if x == i:
      break
  if j >= k:
    max_score = max(max_score,TEMPMAX[k])
  elif SCORE[j] < 0:
    max_score = max(max_score, TEMPMAX[j])
  else:
    m = k//j
    a = SCORE[j] *(m-1) + TEMPMAX[j]
    b = SCORE[j] *m + TEMPMAX[k % j]
    max_score = max(max_score, a, b)
print(max_score)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
check=[-1]*n
finalans=-10**20
for i in range(n):
    if check[i]!=-1:
        continue
    loop=[i]
    now=i
    while p[now]!=i+1:
        check[now]=1
        loop.append(p[now]-1)
        now=p[now]-1
    L=len(loop)
    point=[0]*(L*2)
    point[0]=c[loop[0]]
    for j in range(1,L*2):
        if j<L:
            point[j]=point[j-1]+c[loop[j]]
        else:
            point[j]=point[j-1]+c[loop[j-L]]
    m=-10**20
    if point[L-1]>0:
        r=k%L
        if r==0:
            r=L
        for j in range(1,r+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-j>=0 else point[t]
                m=max(m,cand)
        ans=point[L-1]*(k//L)+m if r!=L else point[L-1]*((k//L)-1)+m
    else:
        for j in range(1,L+1):
            for t in range(j-1,j+L-1):
                cand=point[t]-point[t-j] if t-j>=0 else point[t]
                m=max(m,cand)
        ans=m
    finalans=max(ans,finalans)   
print(finalans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))


def dfs(i):
    if 0 <= visited[i]:
        return
    visited[i] = idx
    cycle.append(i)
    global csum
    csum += C[i]
    dfs(P[i])


visited = [-1]*n
idx = 0
cycles = []
for i in range(n):
    if 0 <= visited[i]:
        continue
    cycle = []
    csum = 0
    dfs(i)
    cycles.append((cycle, csum))
    idx += 1


INF = 10**18
ans = -INF
for i in range(n):
    cycle, csum = cycles[visited[i]]
    cmem = len(cycle)

    if 0 < csum:
        a, b = divmod(k, cmem)
        scoreA = csum*(a-1)
        b += cmem
        score = 0
        scoreB = 0
        for _ in range(b):
            i = P[i]
            score += C[i]
            if scoreB < score:
                scoreB = score
        X = scoreA+scoreB
    else:
        b = min(k, cmem)
        score = 0
        INF = 10**18
        X = -INF
        for _ in range(b):
            i = P[i]
            score += C[i]
            if X < score:
                X = score

    if ans < X:
        ans = X
print(ans)

Solution (Python):
import numpy as np


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

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(np.array(loop))

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        table = np.zeros((loop_len, loop_len), dtype=int)
        table[0] = loop.cumsum()
        table[:, -1] = loop_sum
        for i in range(loop_len - 1):
            table[i + 1, :-1] = (table[i] - loop[i])[1:]
        ans = max(table[:, :min(loop_len, k)].max(), ans)
        if loop_num > 0:
            ans = max(loop_sum * (loop_num - 1) + table[:, :loop_len].max(), ans)
            if loop_mod > 0:
                ans = max(loop_sum * loop_num + table[:, :loop_mod].max(), ans)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        scores += scores * 2
        scores.insert(0, 0)
        acc = list(accumulate(scores))
        tmp = max(max(acc[i + 1:i + m + 1]) - acc[i] for i in range(l))
        ans = max(ans, tmp, loop * d + tmp)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))

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

E=[]
color=["white" for _ in range(N)]
for i in range(N):
    if color[i]=="white":
        index,F=i,[]
        while 1:
            if color[index]=="white":
                color[index]="black"
                index=P[index]-1
                F.append(C[index])
            else:break
        E.append(F)

ans=-float("inf")
for A in E:
    length=len(A)
    if sum(A)<0:
        A=A*2
        for i in range(length):
            point=0
            for j in range(min(K,length)):
                point +=A[i+j]
                ans=max(ans,point)
    else:
        div,mod=divmod(K,length)
        base=(div-1)*sum(A)
        A=A*3
        for i in range(length):
            point=0
            for j in range(mod+length):
                point +=A[i+j]
                ans=max(ans,base+point)
print(ans)

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

to_do = []
res = -float('inf')
for i in range(1,n+1):
    tmp_idx = i
    tmp_val = 0
    tmp_dic = {i:(0,0,i)}
    for j in range(1,min(n+1,k+1)):
        tmp_idx = ps[tmp_idx-1]
        tmp_val += cs[tmp_idx-1]
        res = max(res,tmp_val)
        if tmp_idx not in tmp_dic:
            tmp_dic[tmp_idx] = (j,tmp_val,tmp_idx)
        else:
            if tmp_val > tmp_dic[tmp_idx][1]:
                to_do.append([i,tmp_dic[tmp_idx][0],tmp_dic[tmp_idx][2],tmp_dic[tmp_idx][1],j-tmp_dic[tmp_idx][0],tmp_val-tmp_dic[tmp_idx][1]])
            break

for do in to_do:
    itr = (k - do[1]) // do[4]
    if itr > 0:
        itr -= 1
    remain = k - do[1] - do[4] * itr
    tmp_res = do[3] + itr * do[5]
    res = max(res,tmp_res)
    now = do[2]
    for i in range(remain):
        now = ps[now-1]
        tmp_res += cs[now-1]
        res = max(res, tmp_res)
print(res)

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()]

points = list()
for i in range(N):
    sum = 0
    now = P[i]
    result = list()
    flag = True
    for j in range(N):
        sum += C[now]
        result.append(sum)
        if now == i:
            break
        if j == N-1 and now != i:
            flag = False
        now = P[now]

    if flag:
        points.append(result)
    else:
        
        points.append([-int(1e19)])

ans = -int(1e19)

for i in range(len(points)):
    now = i
    tmpp = 0
    k = K
    while points[now][0] == -int(1e19):
        now = P[now]
        tmpp += C[now]
        k -= 1
        ans = max(ans, tmpp)

    cir = len(points[now])
    cir_point = points[now][cir-1]

    if k <= cir:
        for j in range(k):
            ans = max(ans, points[now][j] + tmpp)
    else:
        if cir_point > 0:
            lm = k // cir - 1
            for j in range(cir):
                ans = max(ans, points[now][j] + lm * cir_point + tmpp)
            for j in range(k % cir):
                ans = max(ans, points[now][j] + (lm + 1) * cir_point + tmpp)
        else:
            for j in range(cir):
                ans = max(ans, points[now][j] + tmpp)

print(ans)

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

P = list(map(lambda x:x-1, P))

ans = -float('inf')
for si in range(N):
    s = []
    tot = 0
    x = si
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x==si:
            break
    l = len(s)
    now = 0
    t = 0
    for i in range(l):
        if i+1 > K: break
        t += s[i]
        now = t
        if tot >0:
            e = (K-(i+1))//l
            now += tot * 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()))
loop = []
visit = [(-1,-1) for i in range(n)]
cou = -1
for i in range(n):
    if visit[i] != (-1,-1):
        continue
    cou += 1
    tyu  = [i]
    now = i
    visit[i] = (cou,0)
    t = 1
    while True:
        nex = p[now] - 1
        if nex == i:
            break
        visit[nex] = (cou,t)
        tyu.append(nex)
        now = nex
        t += 1
    loop.append(tyu)

ans = []

for i in range(n):
    p = loop[visit[i][0]][visit[i][1]:] + loop[visit[i][0]][:visit[i][1]]
    kar = [0]
    kouho = []
    losum = 0
    lokz = len(p)
    for j in p:
        losum += c[j]
        kar.append(kar[-1] + c[j])
    if losum >= 0:
        for l in range(lokz+1):
            if l > k:
                break
            cou = losum*((k-l)//lokz) + kar[l]
            kouho.append(cou)
    elif losum < 0:
        for l in range(1,lokz+1):
            if l > k:
                break
            cou = kar[l]
            kouho.append(cou)
    ans.append(max(kouho))
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**20 * -1
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):
N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

max_score = -1 * float('inf')

for start_pos in range(N):
    step_score = []
    pos = start_pos
    loop_num = 0
    loop_sum = 0
    step = 0
    while (step < K):
        pos = P[pos]
        loop_sum += C[pos]
        step_score.append(loop_sum)
        step += 1
        if pos == start_pos:
            break
    loop_num = step
    step_max_score = max(step_score)
    if loop_num < K:
        if K // loop_num > 0:
            if K % loop_num != 0:
                step_max_score = max(
                    step_max_score,
                    max(step_score[:(K % loop_num)]) + loop_sum * (K // loop_num)
                )
            else:
                step_max_score = max(
                    step_max_score,
                    loop_sum * (K // loop_num)
                )
        if K // loop_num > 1:
            step_max_score = max(
                step_max_score,
                max(step_score) + loop_sum * (K // loop_num - 1)
            )
    max_score = max(step_max_score, max_score)
    

print(max_score)

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()
c = nl()

for i in range(n):
  p[i]-=1

ans = -10**(18)
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):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
p = inpl()
c = inpl()
seen = [False] * n
nums = []
for i in range(n):
    if seen[i]: continue
    seen[i] = True
    res = deque([c[i]])
    now = i
    while True:
        nx = p[now]-1
        if nx == i: break
        res.append(c[nx])
        seen[nx] = True
        now = nx
    nums.append(res)

res = -INF
for num in nums:
    l = len(num)
    su = sum(list(num))
    for _ in range(l): 
        nu = list(num)
        mx = -INF
        now = 0
        for i,x in enumerate(nu):
            if i+1 > k: break
            now += x
            mx = max(now, mx)
        if su > 0:
            now = (k//l-1)*su+mx
            mx = max(now, mx)
            cnt = k//l * l
            now = k//l*su
            for i,x in enumerate(nu):
                if cnt+i+1 > k: break
                now += x
                mx = max(now, mx)
        res = max(res, mx)
        tmp = num.popleft()
        num.append(tmp)
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from itertools import accumulate

def sum_max(line,n_min,n_max):
    n = len(line)
    ac = list(accumulate([0]+line))
    l = 0
    r = n_min
    ans = ac[r]-ac[l]
    i  = 0
    if n_min>n_max:
        ans = 0
    elif n_min==n_max:
        for i in range(n-n_min+1):
            ans = max(ans,ac[i+n_min]-ac[i])
    else:
        while r!=n or i%2==1:
            if i%2==0:
                r = ac[r+1:l+n_max+1].index(max(ac[r+1:l+n_max+1])) + r+1
            else:
                l = ac[l+1:r-n_min+1].index(min(ac[l+1:r-n_min+1])) + l+1
            i+=1
            ans = max(ans,ac[r]-ac[l])
    return ans

def sum_min(line,n_min,n_max):
    n = len(line)
    ac = list(accumulate([0]+line))
    l = 0
    r = n_min
    ans = ac[r]-ac[l]
    i  = 0
    if n_min>n_max:
        ans = 0
    elif n_min==n_max:
        for i in range(n-n_min+1):
            ans = min(ans,ac[i+n_min]-ac[i])
    else:
        while r!=n or i%2==1:
            if i%2==0:
                r = ac[r+1:l+n_max+1].index(min(ac[r+1:l+n_max+1])) + r+1
            else:
                l = ac[l+1:r-n_min+1].index(max(ac[l+1:r-n_min+1])) + l+1
            i+=1
            ans = min(ans,ac[r]-ac[l])
    return ans

def circle_sum_max(circle,n_min,n_max):
    n = len(circle)
    s = sum(circle)
    if n_min>n_max:
        ans = 0
    else:
        ans = max(sum_max(circle,n_min,n_max), s-sum_min(circle,n-n_max,n-n_min))
    return ans

def circle_sum_min(circle,n_min,n_max):
    n = len(circle)
    s = sum(circle)
    if n_min>n_max:
        ans = 0
    else:
        ans = max(sum_min(circle,n_min,n_max), s-sum_max(circle,n-n_max,n-n_min))
    return ans
 
n,k = readints()
p = [x-1 for x in readints()]
c = readints()

circles = []
used = [0]*n

for i in range(n):
    if not used[i]:
        circles.append([c[i]])
        used[i] = 1
        j = p[i]
        while not used[j]:
            circles[-1].append(c[j])
            used[j] = 1
            j = p[j]

score = -10**20

for cir in circles:
    m = len(cir)
    a = sum(cir)
    if k>m:
        if a>0:
            score = max(score, (k//m)*a + circle_sum_max(cir,1,k%m), (k//m-1)*a + circle_sum_max(cir,1,m))
        else:
            score = max(score,circle_sum_max(cir,1,m))
    else:
        score = max(score,circle_sum_max(cir,1,k))

print(score)

Solution (Python):
def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

        def find(self, x):
            if self.par[x] < 0:
                return x
            else:
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.par[x] > self.par[y]:
                x, y = y, x

            self.par[x] += self.par[y]
            self.par[y] = x

        def size(self, x):
            return -self.par[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()

Solution (Python):
def mod_max(loop, mod):
    if mod == 0:
        return 0
    loop_len = len(loop)
    mm = min(loop)
    for start in range(loop_len):
        current_sum = 0
        for i in range(mod):
            current_sum += loop[(start + i) % loop_len]
            mm = max(current_sum, mm)
    return mm


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

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(loop)

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
g = [[0]*(n) for _ in range(n)]
A = [n]*n
















ans = -float('inf')

for i in range(n):
    S = []
    idx = P[i]-1
    S.append(C[idx])
    while idx != i:
        idx = P[idx]-1
        S.append(S[-1] +C[idx])
    v,w = k//len(S),k%len(S)
    if k<=len(S):
        val = max(S[:k])
    elif S[-1]<=0:
        val = max(S)
    else:
        val1 = S[-1] *(v-1)
        val1 += max(S)
        val2 = S[-1]*v
        if w!=0:
            val2 += max(0,max(S[:w]))
        val = max(val1,val2)
    ans = max(ans,val)















print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P = [x - 1 for x in P]
    C = list(map(int, input().split()))
    ans = -(10 ** 18)
    for i in range(N):
        j = i
        S = 0
        L = 0
        for _ in range(K):
            j = P[j]
            S += C[j]
            L += 1
            ans = max(ans, S)
            if j == i:
                break
        if j == i:
            M = max(0, K // L - 1)
            T = S * M
            for _ in range(M * L, K):
                j = P[j]
                T += C[j]
                ans = max(ans, T)
    print(ans)


if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from itertools import accumulate

def sum_max(line,n_min,n_max):
    n = len(line)
    ac = list(accumulate([0]+line))
    l = 0
    r = n_min
    ans = ac[r]-ac[l]
    i  = 0
    if n_min==n_max:
        for i in range(n-n_min+1):
            ans = max(ans,ac[i+n_min]-ac[i])
    else:
        while r!=n or i%2==1:
            if i%2==0:
                r = ac[r+1:l+n_max+1].index(max(ac[r+1:l+n_max+1])) + r+1
            else:
                l = ac[l+1:r-n_min+1].index(min(ac[l+1:r-n_min+1])) + l+1
            i+=1
            ans = max(ans,ac[r]-ac[l])
    return ans

def sum_min(line,n_min,n_max):
    n = len(line)
    ac = list(accumulate([0]+line))
    l = 0
    r = n_min
    ans = ac[r]-ac[l]
    i  = 0
    if n_min==n_max:
        for i in range(n-n_min+1):
            ans = min(ans,ac[i+n_min]-ac[i])
    else:
        while r!=n or i%2==1:
            if i%2==0:
                r = ac[r+1:l+n_max+1].index(min(ac[r+1:l+n_max+1])) + r+1
            else:
                l = ac[l+1:r-n_min+1].index(max(ac[l+1:r-n_min+1])) + l+1
            i+=1
            ans = min(ans,ac[r]-ac[l])
    return ans

def circle_sum_max(circle,num):
    n = len(circle)
    s = sum(circle)
    if num == 0:
        ans = 0
    else:
        ans = max(sum_max(circle,1,num), s-sum_min(circle,n-num,n-1))
    return ans
 
n,k = readints()
p = [x-1 for x in readints()]
c = readints()

circles = []
used = [0]*n

for i in range(n):
    if not used[i]:
        circles.append([c[i]])
        used[i] = 1
        j = p[i]
        while not used[j]:
            circles[-1].append(c[j])
            used[j] = 1
            j = p[j]

score = -10**20

for cir in circles:
    m = len(cir)
    a = sum(cir)
    if k>m:
        if a>0:
            score = max(score, (k//m)*a + circle_sum_max(cir,k%m), (k//m-1)*a + circle_sum_max(cir,m))
        else:
            score = max(score,circle_sum_max(cir,m))
    else:
        score = max(score,circle_sum_max(cir,k))

print(score)

Solution (Python):
n, k = (int(x) for x in input().split())
P = list(int(x) - 1 for x in input().split())
C = list(int(x) for x in input().split())

ans = -1e18
for si in range(n):
    S = [C[si]]
    x = P[si]
    while x != si:
        S.append(S[-1] + C[x])
        x = P[x]
    m = len(S)
    if k <= m:
        tmp = max(S[:k])
    else:
        loop = k // m
        r = k % m
        tmp = max(S[-1] * (loop - 1) + max(S), max(S))
        if r != 0:
            tmp = max(tmp, S[-1] * loop + max(S[:r]))
    ans = max(ans, tmp)
print(ans)

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

ans=max(c)
if ans<0:
    print(ans)
    exit()

for i in range(n):
    
    nxt=i
    lp=[]
    while 1:
        nxt=p[nxt]
        lp.append(nxt)
        if nxt==i:
            break
    lpc=max(0,sum(c[x] for x in lp))
    nxt=i
    lpl=len(lp)
    wks=0
    
    for j in range(lpl):
        nxt=p[nxt]
        wks+=c[nxt]
        
        
        
        
        
        ans=max(ans,(k-j-1)//lpl*lpc+wks,wks)
        
        if j==k-1:
            break
print(ans)