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):



def solve():
    N, K = list(map(int, input().split()))
    Ps = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    
    ans = -float("inf")
    for i in range(N):
        ans = max(ans, Cs[i])

    if K == 1:
        print(ans)
        return

    loop_list = []
    for start in range(N):
        now = start
        visited = set()
        visited.add(now)
        move = 0
        total_score = 0
        max_score = ans

        while True:  
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            move += 1
            now = nx
            if now in visited:
                
                if total_score > 0:
                    
                    loop_list.append((start, total_score, move))
                break

            
            if move == K:
                
                break
            visited.add(now)
        ans = max(ans, max_score)


    
    for start, score, move in loop_list:
        total_score = score*(K//move)
        restK = K % move
        max_score = total_score

        
        now = start
        while restK != 0:
            restK -= 1
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            now = nx
        ans = max(ans, max_score)

        
        now = start
        total_score = score*(K//move) - score
        max_score -= total_score
        for i in range(move):
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            now = nx
        ans = max(ans, max_score)

    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys, math
import io, os

from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction

INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
ans=-INF
for i in range(n):
    c1=[]
    a=i
    while True:
        a=p[a]-1
        c1.append(c[a])
        if a==i:
            break
    m1=0
    for j in range(min(k,len(c1))):
        m1+=c1[j]
        ans=max(m1,ans)
    if m1>0:
        t=k//len(c1)
        m1=max(0,m1*(t-1))
        ind=max(0,len(c1)*(t-1))
        ans=max(ans,m1)
        for i in range(ind,k):
            m1+=c1[i%len(c1)]
            ans=max(ans,m1)
out(ans)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n,k=MI()
	P=LI()
	for i in range(n):
		P[i]-=1
	C=LI()

	A=[[] for _ in range(n)]

	for i in range(n):
		A[i].append(C[i])
		now=P[i]
		while i!=now:
			A[i].append(A[i][-1]+C[now])
			now=P[now]
	

	ans=-10**18

	for i in range(n):
		l=len(A[i])
		q,r=divmod(k-1,l)

		if q==0:
			ans=max(ans,max(A[i][:k]))
		else:
			if A[i][-1]<=0:
				ans=max(ans,max(A[i]))
			else:
				ans=max(ans,A[i][-1]*(q-1)+max(A[i]),A[i][-1]*(q)+max(A[i][:r+1]))

	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()))
l = [[] for i in range(n)]
for i in range(n):
    l2 = [i + 1]
    cnt = 0
    while True:
        l2.append(p[l2[-1] - 1])
        cnt += c[l2[-1] - 1]
        l[i].append(cnt)
        if l2[-1] == i + 1:
            break
ans = -float("inf")
for i in range(n):
    le = len(l[i])
    for j in range(min(k, le)):
        cnt = l[i][j]
        if l[i][-1] > 0:
            cnt += (k - j - 1) // le * l[i][-1]
        ans = max(ans, cnt)
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()))

ans=0
check=set()

for i in range(N):
    
    if i in check:
        continue
    
    
    tmpK=K
    tmpans=0
    loop_check=set()
    tmp_idx=i
    loop=[]
    while tmp_idx not in loop_check:
        loop.append(C[tmp_idx])
        loop_check.add(tmp_idx)
        check.add(tmp_idx)
        tmp_idx=P[tmp_idx]
    
    S=sum(loop)
    L=len(loop)
    if S>=0 and tmpK//L>=2:
        tmpans=S*(tmpK//L-1)
        tmpK=tmpK%L+L
    
    
    
    loop=[0]+loop*3
    for i in range(len(loop)-1):
        loop[i+1]+=loop[i]
    n=3*L+1
    def init_min(init_min_val):
        
        for i in range(n):
            seg_min[i+num_min-1]=init_min_val[i]    
        
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res
    
    ide_ele_min = 10**15
    
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    init_min(loop)
    local_max=0
    for i,v in enumerate(loop):
        if i>=1:
            
            local_max=max(local_max,v-query_min( max(0,i-tmpK),i ) )
    
    ans=max(ans,local_max+tmpans)

if ans==0:
    print(max(C))
else:
    print(ans)

Solution (Python):
import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    P = list(mi())
    C = list(mi())

    
    loops = []
    
    done = [False]*N
    
    for i in range(N):
        
        if done[i]:
            continue

        now = P[i]-1
        T = 1
        s = C[now]
        lst = [now]

        done[now] = True

        
        while now != i:
            now = P[now]-1
            T += 1
            s += C[now]
            lst.append(now)

            done[now] = True

        loops.append((T, s, lst))

    

    ans = -math.inf

    
    for loop in loops:
        
        T, s, lst = loop

        if s <= 0:
            m = -math.inf
            for v in lst:
                now = v
                ss = 0
                for _ in range(min(K, T)):
                    now = P[now]-1
                    ss += C[now]
                    m = max(m, ss)

            ans = max(ans, m)

        else:
            n = max(K//T-1, 0)
            rest = K-n*T
            m = -math.inf

            for v in lst:
                now = v
                ss = 0
                for _ in range(rest):
                    now = P[now]-1
                    ss += C[now]
                    m = max(m, ss)
            
            ans = max(ans, m+n*s)
    print(ans)



if __name__ == '__main__':
    main()

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

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        
        
        
        
        

        
        
        
        

        cnt = 0
        for rem in range(1, min(L, K) + 1):
            cnt += costs[(i + rem) % L]
            val1 = cnt
            val2 = cnt + (K - rem) // L * S
            ans[v] = max(ans[v], val1, val2)

print(max(ans))

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



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


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().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())


def main():
    n, k = ns()
    p = na1()
    c = na()

    uf = UnionFind(n)
    for i, pi in enumerate(p):
        uf.union(i, pi)

    cycledist = [[-INF for _ in range(2)] for __ in range(n)]
    for lis in uf.all_group_members().values():
        tmp = 0
        l = len(lis)
        for idx in lis:
            tmp += c[idx]
            cycledist[idx][1] = l
        for idx in lis:
            cycledist[idx][0] = tmp

    ans = -INF

    for i in range(n):
        flg = k // cycledist[i][1] > 0
        tmp_ans = cycledist[i][0] * ((k // cycledist[i][1]) - 1) if flg else 0

        tmp = 0
        idx = i
        for j in range(cycledist[i][1] * flg + k % cycledist[i][1]):
            tmp += c[p[idx]]
            idx = p[idx]
            ans = max(ans, tmp_ans + tmp)

        tmp = 0
        idx = i
        for j in range(min(k, cycledist[i][1])):
            tmp += c[p[idx]]
            idx = p[idx]
            ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import copy

def cost_val(visit_list, P, C):
    maxval = [-10**10] * (len(P) + 1)
    for start_idx in visit_list:
        cost = 0
        now_id = start_idx
        for i in range(len(visit_list)):
            now_id = P[now_id]
            cost += C[now_id]
            maxval[i + 1] = max(maxval[i + 1], cost)
    return maxval[1:len(visit_list) + 1]

def cycles(P):
    cycle_list = []
    visit_list = [False] * len(P)
    for i in range(len(P)):
        if visit_list[i]:
            continue
        now_id = i
        cycle = []
        for j in range(len(P)):
            if visit_list[now_id]:
                break
            cycle.append(now_id)
            visit_list[now_id] = True
            now_id = P[now_id]
        cycle_list.append(cycle)
    return cycle_list

def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))
    cycle_list = cycles(P)
    ans = max(C)
    for cycle in cycle_list:
        maxval = cost_val(cycle, P, C)
        if len(cycle) > K:
            ans = max(ans, max(maxval[:K]))
        else:
            if K % len(cycle) == 0:
                ans = max(ans, max(maxval), max(map(lambda x: x + maxval[-1] * (K // len(cycle) - 1), maxval)), maxval[-1] * (K // len(cycle)))
            else:
                ans = max(ans, max(maxval), max(map(lambda x: x + maxval[-1] * (K // len(cycle) - 1), maxval)), maxval[-1] * (K // len(cycle)) + max(maxval[:(K % len(cycle))]))
    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):

def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    cycles = []
    ans = -INF
    for n in range(N):
        loop, score = 0, 0
        t = n
        for i in range(min(N, K)):
            n = P[n]
            score += C[n]
            ans = max(ans, score)
            if n == t:
                loop = i + 1
                break
        cycles.append((loop, score))

    for n in range(N):
        loop, score = cycles[n]
        if loop > 0 and score > 0:
            r = (K - 1) // loop
            nscore = r * score
            for i in range(K - r * loop):
                n = P[n]
                nscore += C[n]
                ans = max(nscore, ans)
    print(ans)



if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import defaultdict
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = max(C[1:])

for init in range(1, N + 1):   
    score = defaultdict(int)  
    visited = [-1] * (N + 1)
    visited[init] = 0  
    i = init
    for k in range(1, K + 1):
        prev = i
        i = P[i]    

        if visited[i] < 0:  
            visited[i] = k
            score[i] = score[prev] + C[i]
            max_score = max(max_score, score[i])
            continue

        loop_score = (score[prev] + C[i]) - score[i]
        loop_len = k - visited[i]

        score[i] = score[prev] + C[i]

        loop_num = (K - k) // loop_len 
        loop_rem = (K - k) % loop_len

        if loop_num > 0 and loop_rem == 0:
            loop_num -= 1
            loop_rem = loop_len

        j = i   
        temp = 0
        rem_max = 0
        for _ in range(loop_rem):
            j = P[j]
            temp += C[j]
            rem_max = max(rem_max, temp)

        max_score = max(max_score, score[i] + loop_num * loop_score + rem_max)
        break

print(max_score)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  
  
  

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1])) 
    else:
      ans=max(ans,max(l[i][1:K+1])) 

      
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans1=c*l[i][roop_count]
        k=K%roop_count
        _ans1+=max(l[i][1:k+1]+[0])
        ans=max(ans,_ans1)

        
        _ans2=(c-1)*l[i][roop_count]
        _ans2+=max(l[i][:roop_count]+[0])
        ans=max(ans,_ans1,_ans2)

  return ans


print(main())

Solution (Python):
import sys
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()))
ans = -float('inf')
for s in range(N):
    scores = [0] * (N+1)
    i = P[s]
    v = scores[i] = C[i]
    l = 1
    while i != s:
        i = P[i]
        v += C[i]
        scores[i] = v
        l += 1
    i = P[s]
    c = 1
    ans = max(ans, scores[i], scores[i] + (K - c) // l * v)
    while i != s and c < K:
        i = P[i]
        c += 1
        ans = max(ans, scores[i], scores[i] + (K - c) // l * v)
print(ans)

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

reach = [False]*n
x = []
for i in range(n):
    if reach[i]:continue
    buf = []
    cur = i
    while not reach[cur]:
        buf.append(c[cur])
        reach[cur] = True
        cur = p[cur]
    x.append(buf)

ans = max(c)
import itertools
for i in x:
    n = k//len(i)
    ind = k%len(i)
    if n>0:
        n -= 1
        ind += len(i)
    else:
        ind = min(k,len(i)*2)
    ii = i+i+i
    r = list(itertools.accumulate(ii))
    a = max(0,r[len(i)-1]*n)
    for j in range(len(i)):
        for z in range(1,ind+1):
            s = r[j+z]-r[j]
            ans = max(ans,a+s)
print(ans)

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

reach = [False]*n
x = []
for i in range(n):
    if reach[i]:continue
    buf = []
    cur = i
    while not reach[cur]:
        buf.append(c[cur])
        reach[cur] = True
        cur = p[cur]
    x.append(buf)

ans = max(c)
import itertools
for i in x:
    n = k//len(i)
    ind = k%len(i)
    if n>0:
        n -= 1
        ind += len(i)
    else:
        ind = min(k,len(i)*2)
    ii = i+i+i
    r = list(itertools.accumulate(ii))
    a = max(0,r[len(i)-1]*n)
    for j in range(len(i)):
        for z in range(1,ind+1):
            s = r[j+z]-r[j]
            if z<ind+1:ans = max(ans,a+s)
            else:ans = max(ans,s)
print(ans)

Solution (Python):

def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    visited = [0] * N
    cycles = []

    for i in range(N):
        if visited[i]:
            continue
        score = []
        v = i
        visited[v] = True
        score.append(C[v])
        while not visited[P[v]]:
            v = P[v]
            visited[v] = True
            score.append(C[v])
        cycles.append(score)

    ans = -INF
    for cy in cycles:
        length = len(cy)
        c_num = max(0, (K - 1) // length - 1)
        total = max(0, sum(cy) * c_num)
        rest = K - (c_num * length)
        l_cy = cy + cy + cy
        for l in range(length):
            total_rest = 0
            for diff in range(rest):
                total_rest += l_cy[l + diff]
                ans = max(ans, total + total_rest)

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
def max2(x,y):
    return x if x > y else y

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

off = max(C)
m2 = off
for i in range(N):
    tmp = 0
    m1 = off
    l = i
    S = 0
    k = 0
    for j in range(N):
        S += C[l]
        l = P[l] - 1
        if l==i:
            k = j+1
            break
    cnt = K // k - (K % k == 0)
    cnt = max2(0, cnt -2)
    a = K-cnt*k
    l = i
    for j in range(a):
        tmp += C[l]
        m1 = max2(m1, tmp)
        l = P[l] - 1
    if S > 0:
        m1 += cnt*S
    m2 = max2(m1, m2)

print(m2)
"""
2 4
2 1
10 -7
"""

Solution (Python):
from collections import defaultdict
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = max(C[1:])

for init in range(1, N + 1):   
    score = defaultdict(int)  
    visited = [-1] * (N + 1)
    visited[init] = 0  
    i = init
    for k in range(1, K + 1):
        prev = i
        i = P[i]    

        if visited[i] < 0:  
            visited[i] = k
            score[i] = score[prev] + C[i]
            max_score = max(max_score, score[i])
            continue

        loop_score = (score[prev] + C[i]) - score[i]
        loop_len = k - visited[i]

        score[i] = score[prev] + C[i]
        

        
        

        start = i   
        loop_num = (K - k) // loop_len 
        loop_rem = (K - k) % loop_len

        if loop_num > 0 and loop_rem == 0:
            loop_num -= 1
            loop_rem = loop_len

        jj = start
        temp = 0
        temp_max = 0
        for l in range(loop_rem):
            jj = P[jj]
            temp += C[jj]
            temp_max = max(temp_max, temp)

        loop_max = temp_max + loop_num * loop_score
        max_score = max(max_score, score[start] + loop_max)
        break

print(max_score)

Solution (Python):
from collections import deque

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

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    score = deque([0])
    while j < k:
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if now == i:
            break
    ans = max(ans, max(list(score)[1:]))
    if j < k and score[-1] > 0:
        loop_num = k//j
        rest = k%j
        ans = max(ans, max(list(score)[:rest+1])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )
print(ans)

Solution (Python):
from collections import deque

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

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    score = deque([0])
    while j < k:
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if now == i:
            break
    ans = max(ans, max(list(score)[1:]))
    if j < k and score[-1] > 0:
        loop_num = k//j
        rest = k%j
        ans = max(ans, max(list(score)[:rest+1])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )
print(ans)

Solution (Python):
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n,k = [int(x) for x in input().split()]
perm  =  [int(x)-1 for x in input().split()]
cost = [int(x) for x in input().split()]


ans = -10**10
for node in xrange(n):
    visited = [False for _ in xrange(n)]
    curnode = perm[node]
    cost_lst = [0]
    while not visited[curnode]:
        visited[curnode] = True
        cost_lst.append(cost_lst[-1] + cost[curnode])
        curnode = perm[curnode]

    cycles_n = k // (len(cost_lst)-1)
    rem = k % (len(cost_lst)-1)

    
    if cycles_n > 0:
        ans = max(ans, max(cost_lst[1:]))
    if cycles_n == 0:
        ans = max(ans, max(cost_lst[1:rem+1]))
    if cycles_n > 0 and cost_lst[-1] > 0:
        if rem != 0:
            opt1 = cycles_n * cost_lst[-1] + max(cost_lst[1:rem+1])
        else:
            opt1 = (cycles_n-1) * cost_lst[-1] + max(cost_lst[1:])
        ans = max(ans, opt1)

print(ans)

Solution (Python):
def mss(l,length,k):
    x = - 1000000001
    for i in range(length):
        temp = 0
        for j in range(i,i+k):
            temp += l[j]
            if temp > x:
                x = temp
    return x
  
def mss2(l,length,total,k):
    x = - 1000000001
    if k <= length:
      for i in range(length):
          temp = 0
          for j in range(i,i+k):
              temp += l[j]
              if temp > x:
                  x = temp
      return x
    else:
      for i in range(length):
          temp = 0
          for j in range(i,i+length):
              temp += l[j]
              r = j - i + 1
              if temp + (total * ((k-r) // length)) > x:
                  x = temp + (total * ((k-r) // length))
      return x
      

if __name__ == '__main__':
    N,K = map(int,input().split())
    P = [int(p)-1 for p in input().split()]
    C = [int(c) for c in input().split()]
    
    L_close = []
    Done = [0] * N
    for i in range(N):
        if Done[i] == 1:
            continue
        score = []
        
        Done[i] = 1
        
        p = P[i]
        Done[p] = 1
        score.append(C[p])
        while p != i:
            p = P[p]
            Done[p] = 1
            score.append(C[p])
        L_close.append(score)
    
    ans = - 1000000001
    for l in L_close:
        total = sum(l)
        length = len(l)
        l = l + l
        if total <= 0:
            ans = max(ans,mss(l,length,min(K,length)))
        else:
            ans = max(ans,mss2(l,length,total,K))
    print(ans)

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

C = list(map(int,input().split()))
Flag = True
for c in C:
  if c >= 0:
    Flag = False
    break
if Flag:
  print(max(C))
  exit()
L = []
for i in range(N):
  
  Flag = False
  now = i
  temp = []
  while True:
    if Flag and now == i:
      break
    nxt = P[now]
    Flag = True
    temp.append(C[nxt])
    now = nxt
  L.append(temp)

ans = 0
S = []
for X in L:
  start = [0]
  for i in range(len(X)):
    temp = start[-1]+X[i]
    start.append(temp)
  S.append(start)

for X,SS in zip(L,S):
  n = len(X)
  cycle_sum = SS[-1]
  if K <= n:
    kouho = max(SS[:K+1])
  elif cycle_sum < 0:
    kouho = max(SS)
  else:
    amari = K%n
    loop = K//n
    first = 0 
    second = 0 
    first = (loop-1)*cycle_sum + max(SS)
    second = loop*cycle_sum + max(SS[:amari+1])
    kouho = max(first,second)
  ans = max(ans,kouho)
print(ans)

Solution (Python):
from collections import defaultdict
INF = float('inf')
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = -INF
for init in range(1, N + 1):   
    score = defaultdict(int)  
    visited = [-1] * (N + 1)
    visited[init] = 0  
    i = init
    
    for k in range(1, K + 1):
        prev = i
        i = P[i]    

        if visited[i] < 0:  
            visited[i] = k
            score[i] = score[prev] + C[i]
            
            max_score = max(max_score, score[i])
            continue

        loop_score = (score[prev] + C[i]) - score[i]
        loop_len = k - visited[i]

        score[i] = score[prev] + C[i]
        
        max_score = max(max_score, score[i])

        if k == K:
            break 

        start = i   
        loop_num = (K - k) // loop_len 
        loop_rem = (K - k) % loop_len

        if loop_rem == 0:
            loop_num -= 1
            loop_rem = loop_len

        jj = start
        temp = 0
        temp_max = 0
        for l in range(loop_rem):
            jj = P[jj]
            temp += C[jj]
            temp_max = max(temp_max, temp)

        loop_max = temp_max + loop_num * loop_score
        
        max_score = max(max_score, score[start] + loop_max)
        break

    

if max_score == -INF:
    max_score = max(C[1:])

print(max_score)

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



def main():
    n, k = [int(i) for i in input().strip().split()]
    p = [int(i) for i in input().strip().split()]
    c = [int(i) for i in input().strip().split()]
    ans = -10**9
    for i in range(n):
        scores = [0]
        seen = set([i])
        now = i
        loop = False
        for _ in range(k):
            now = p[now] - 1
            scores.append(c[now])
            if now in seen:
                loop = True
                break
            seen.add(now)
        for i in range(len(scores) - 1):
            scores[i + 1] += scores[i]
        tmp = max(scores[1:])
        ans = max(ans, tmp)
        if (not loop) or scores[-1] <= 0:
            continue
        tmp = scores[-1] * (k // (len(scores) - 1))
        rem = k % (len(scores) - 1)
        tmp += max(scores[:rem + 1])
        ans = max(ans, tmp)
        tmp = scores[-1] * (k // (len(scores) - 1) - 1)
        tmp += max(scores)
        ans = max(ans, tmp)
    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()))
ans = -float("inf")
for i in range(N):
    hoge = []
    p = i
    s = 0
    for j in range(K):
        p = P[p]-1
        s += C[p]
        hoge.append(s)
        ans = max(ans,s)
        if p == i:
            S1 = s*((K-1)//len(hoge))
            S1 += max(hoge[0:(K-1)%len(hoge)+1])
            S2 = ans
            if (K-1) // len(hoge) > 1:
                S2 = s*((K-1)//len(hoge)-1)
                S2 += max(hoge)
            ans = max(ans,S1,S2)
            break
print(ans)